Longest Subarray with At Most K Distinct
Python
Hard
3 views
Problem Description
Read n integers and K. Compute length of the longest contiguous subarray that has at most K distinct numbers.
Input Format
First line n K. Second line n integers.
Output Format
One integer maxLen.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0]); K=int(p[1])
a=list(map(int,p[2:2+n]))
count={}
left=0
best=0
dist=0
for right in range(n):
v=a[right]
if count.get(v,0)==0:
dist+=1
count[v]=count.get(v,0)+1
while dist>K:
lv=a[left]
count[lv]-=1
if count[lv]==0:
del count[lv]
dist-=1
left+=1
ln=right-left+1
if ln>best:
best=ln
sys.stdout.write(str(best))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!