Subarrays With At Least N Distinct Integers

Question

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

• tsh: 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?
• user101295: @tsh Good question, I've changed the wording.
• Kaddath: 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

Answer 1

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!

• user81655: 93 bytes
• user81655: Alternatively 101 bytes where it doesn't fail for large inputs due to recursion limit in above solution
• Arnauld: @user81655 Thank you! I golfed a few more bytes by starting from the end of the sequence and getting rid of L.
• tsh: 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')
• Arnauld: @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!

Answer 2

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!

• dingledooper: @Noodle9 Thank you, didn't realize that was possible.
• tsh: 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.
• dingledooper: @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.

Answer 3

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).

• rydwolf: Welcome to Code Golf! Nice golf.
• l4m2: Isn't it max(a) init len(a)*n time?

Answer 4

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.

• ovs: 157 bytes (removed some parentheses, for loop, dict.get and avoiding ifs)
• Jonathan Allan: Save another five by starting at b and counting down TIO.
• Noodle9: @ovs Wow amazing - thanks! :D
• Noodle9: @JonathanAllan Just when I thought it couldn't get any better... very nice - thanks! :D

Answer 5

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!