# Subarrays With At Least N Distinct Integers

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
• 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?
– tsh
Mar 9, 2021 at 1:18
• @tsh Good question, I've changed the wording. Mar 9, 2021 at 1:24
• 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 Mar 9, 2021 at 13:48

# 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!

• 93 bytes Mar 9, 2021 at 2:46
• Alternatively 101 bytes where it doesn't fail for large inputs due to recursion limit in above solution Mar 9, 2021 at 2:49
• @user81655 Thank you! I golfed a few more bytes by starting from the end of the sequence and getting rid of L. Mar 9, 2021 at 8:35
• 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')
– tsh
Mar 9, 2021 at 9:29
• @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! Mar 9, 2021 at 10:13

# 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!

• @Noodle9 Thank you, didn't realize that was possible. Mar 9, 2021 at 3:15
• 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.
– tsh
Mar 9, 2021 at 10:40
• @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. Mar 9, 2021 at 17:48

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

• Welcome to Code Golf! Nice golf. Mar 10, 2021 at 0:58
• Isn't it max(a) init len(a)*n time?
– l4m2
Mar 21, 2021 at 10:59

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

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

# 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!