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
Improve this question
\$\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\$ Commented Mar 9, 2021 at 1:18
  • 1
    \$\begingroup\$ @tsh Good question, I've changed the wording. \$\endgroup\$ Commented Mar 9, 2021 at 1:24
  • 2
    \$\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\$ Commented Mar 9, 2021 at 13:48

5 Answers 5

Reset to default
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!

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 93 bytes \$\endgroup\$ Commented Mar 9, 2021 at 2:46
  • \$\begingroup\$ Alternatively 101 bytes where it doesn't fail for large inputs due to recursion limit in above solution \$\endgroup\$ Commented Mar 9, 2021 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\$ Commented Mar 9, 2021 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\$ Commented Mar 9, 2021 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\$ Commented Mar 9, 2021 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!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ @Noodle9 Thank you, didn't realize that was possible. \$\endgroup\$ Commented Mar 9, 2021 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\$ Commented Mar 9, 2021 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\$ Commented Mar 9, 2021 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).

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf! Nice golf. \$\endgroup\$ Commented Mar 10, 2021 at 0:58
  • \$\begingroup\$ Isn't it max(a) init len(a)*n time? \$\endgroup\$ Commented Mar 21, 2021 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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ 157 bytes (removed some parentheses, for loop, dict.get and avoiding ifs) \$\endgroup\$ Commented Mar 9, 2021 at 13:34
  • \$\begingroup\$ Save another five by starting at b and counting down TIO. \$\endgroup\$ Commented Mar 9, 2021 at 17:59
  • \$\begingroup\$ @ovs Wow amazing - thanks! :D \$\endgroup\$ Commented Mar 9, 2021 at 18:26
  • \$\begingroup\$ @JonathanAllan Just when I thought it couldn't get any better... very nice - thanks! :D \$\endgroup\$ Commented Mar 9, 2021 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!

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.