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

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!

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!

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

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.

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!