12
\$\begingroup\$

Given a sequence of integers and an integer N, output the number of contiguous subsequences that contain at least N distinct integers. Each integer in the sequence is non-negative and will not be larger than the size of the sequence.

For example, with the sequence 1,2,2,3 and N=2, there are 5 contiguous subsequences that contain at least 2 distinct integers:

1,2
1,2,2
2,2,3
2,3
1,2,2,3

The asymptotic time complexity must be linearithmic in the size of the input sequence. (The time complexity must be at most amortized O(S*logS) where S is the size of the input sequence.)

Testcases:

Sequence N Output
1,2,3 2 3
1,2,2,3 2 5
6,1,4,2,4,5 3 9
1,1,2,2,2,3,4,4 4 4
8,6,6,1,10,5,5,1,8,2 5 11
https://pastebin.com/E8Xaej8f (1,000 integers) 55 446308
https://pastebin.com/4aqiD8BL (80,000 integers) 117 3190760620
\$\endgroup\$
3
  • \$\begingroup\$ As the question says "be at most O(S*logS) in the worst case", to my understanding: For example, an implementation loops O(S) times, each time it access some value in a Hash Set with size O(S). And the HashSet's implementation has O(S) time complexity in worst case. The implementation is invalid to this question. Is this correct? \$\endgroup\$ – tsh Mar 9 at 1:18
  • 1
    \$\begingroup\$ @tsh Good question, I've changed the wording. \$\endgroup\$ – user101295 Mar 9 at 1:24
  • 1
    \$\begingroup\$ Is there an objective reason for limiting most of your challenges to a given time complexity? IMO it restricts a lot the golfing creativity, and I fail to see what good it brings in these cases \$\endgroup\$ – Kaddath Mar 9 at 13:48
5
\$\begingroup\$

JavaScript (ES6), 93 bytes

Saved 18 bytes thanks to @user81655
Saved 2 bytes thanks to @tsh

Expects (N)(sequence).

n=>C=a=>eval('for(i=j=a.length,c=s=0;~j;c+=c<n?(C[v=a[--j]]=-~C[v])<2:-!--C[s-=~j,a[--i]])s')

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ 93 bytes \$\endgroup\$ – user81655 Mar 9 at 2:46
  • \$\begingroup\$ Alternatively 101 bytes where it doesn't fail for large inputs due to recursion limit in above solution \$\endgroup\$ – user81655 Mar 9 at 2:49
  • \$\begingroup\$ @user81655 Thank you! I golfed a few more bytes by starting from the end of the sequence and getting rid of L. \$\endgroup\$ – Arnauld Mar 9 at 8:35
  • 1
    \$\begingroup\$ Whenever you write return, you may change it to eval: n=>C=a=>eval('for(i=j=a.length,c=s=0;~j;c+=c<n?(C[v=a[--j]]=-~C[v])<2:-!--C[s-=~j,a[--i]])s') \$\endgroup\$ – tsh Mar 9 at 9:29
  • \$\begingroup\$ @tsh eval() is so bad that I'm reluctant to use it even in golfed code. :-p But it's OK here since this code is fast by definition. Thank you! \$\endgroup\$ – Arnauld Mar 9 at 10:13
4
\$\begingroup\$

C (gcc), 108 104 bytes

-4 bytes thanks to @Noodle9

Takes three inputs, \$ A \$ (the array), \$ S \$ (the size of the array), and \$ N \$ (the minimum distinct integers allowed).

s;f(A,S,N)int*A;{int c[1<<20]={},n=0,l=S;for(s=S*S;S;s-=l)for(n+=!c[A[--S]]++;n/N;)n-=!--c[A[--l]];s=s;}

The two-pointer method is used to achieve a runtime of \$ O(S) \$. Note that the c[1<<20] automatically caps the input \$ S \$ at \$ 2^{10} \$, but it can be adjusted to meet the constraints.

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ @Noodle9 Thank you, didn't realize that was possible. \$\endgroup\$ – dingledooper Mar 9 at 3:15
  • \$\begingroup\$ if i understand correctly, this code’s time complexity relays on the max number of input array which could be as large as S^2. \$\endgroup\$ – tsh Mar 9 at 10:40
  • \$\begingroup\$ @tsh Yes that's right. Alternatively a hash table would have to be used if the max number was something arbitrary. But it's O(S) in this case because the statement mentions that the number will not exceed S. \$\endgroup\$ – dingledooper Mar 9 at 17:48
3
\$\begingroup\$

Python 3.8 (pre-release), 138 bytes

def f(a,n):
 c=0;l=1+max(a);m=[0]*l;j=len(a)
 for v in a:
  while(n>(d:=l-m.count(0)))*j:m[a[-j]]+=1;j-=1
  c-=~j*(d>=n);m[v]-=1
 return c

Try it online!

Credit to Noodle9 for the overall idea. I would have just commented on that answer but I am a new user with no rep, so I have to post a new one, sorry!

Doing away with the dictionary and its method calls saves 11 bytes (at the cost of requiring Python 3.8, though I have a different solution saving 4 bytes without the walrus). We can save another 3 bytes by replacing a[S-j] with a[-j] and doing away with S (4 bytes if used twice as in the original answer).

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf! Nice golf. \$\endgroup\$ – Redwolf Programs Mar 10 at 0:58
  • \$\begingroup\$ Isn't it max(a) init len(a)*n time? \$\endgroup\$ – l4m2 Mar 21 at 10:59
2
\$\begingroup\$

Python 3, 189 \$\cdots\$ 157 152 bytes

Saved a whopping 16 32 bytes thanks to ovs!!!
Saved 5 bytes thanks to Jonathan Allan!!!

def f(a,n):
 c=0;m={};S=j=len(a)
 for v in a:
  while(n>len(m))*j:m[a[S-j]]=m.get(a[S-j],0)+1;j-=1
  c-=~j*(len(m)>=n);m[v]-=1;m[v]<1<m.pop(v)
 return c

Try it online!

Has \$O(S)\$ time complexity.

\$\endgroup\$
4
  • \$\begingroup\$ 157 bytes (removed some parentheses, for loop, dict.get and avoiding ifs) \$\endgroup\$ – ovs Mar 9 at 13:34
  • \$\begingroup\$ Save another five by starting at b and counting down TIO. \$\endgroup\$ – Jonathan Allan Mar 9 at 17:59
  • \$\begingroup\$ @ovs Wow amazing - thanks! :D \$\endgroup\$ – Noodle9 Mar 9 at 18:26
  • \$\begingroup\$ @JonathanAllan Just when I thought it couldn't get any better... very nice - thanks! :D \$\endgroup\$ – Noodle9 Mar 9 at 18:27
0
\$\begingroup\$

JavaScript (Node.js), 82 78 bytes

n=>s=>s.map(A=_=>{for(n-=!A[_],A[_]=-~A[_];!n;)n+=!--A[s[i++]];m+=i},i=m=0)&&m

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.