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

5 Answers 5

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, 2021 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, 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\$
    – Arnauld
    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\$
    – tsh
    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\$
    – Arnauld
    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!

\$\endgroup\$
3
  • \$\begingroup\$ @Noodle9 Thank you, didn't realize that was possible. \$\endgroup\$ 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\$
    – tsh
    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\$ 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).

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

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

\$\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.