Distinct In Every Window
Hard
Programming Interview
Algorithms
13 views
Problem Statement
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.
Example
1 7 4 1 2 1 3 4 2 3
3 4 4 3
Constraints
Sum of n over all testcases
Input / Output Format
Input Format
First integer t. For each: n k then n ints.
Output Format
t lines window distinct counts.
Constraints
Sum of n over all testcases
Examples
Input:
1
7 4
1 2 1 3 4 2 3
Output:
3 4 4 3
Example Solution (Public)
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))
Official Solution Code
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))
Please login to submit solutions.