Distinct In Every Window
Programming Interview
Hard
5 views
Problem Description
For each testcase you get n, k and n integers. For each window of size k output how many distinct numbers are inside.
Input Format
First integer t. For each: n k then n ints.
Output Format
t lines window distinct counts.
Sample Test Case
Input:
1
7 4
1 2 1 3 4 2 3
Constraints
Sum of n over all testcases
Official Solution
import sys
from collections import defaultdict
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it)); k=int(next(it))
a=[int(next(it)) for _ in range(n)]
freq=defaultdict(int)
distinct=0
ans=[]
for i in range(n):
if freq[a[i]]==0:
distinct+=1
freq[a[i]]+=1
if i>=k:
x=a[i-k]
freq[x]-=1
if freq[x]==0:
distinct-=1
if i>=k-1:
ans.append(str(distinct))
out.append(' '.join(ans))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!