Two-Pointer Method: Smallest Subarray with K Distinct Elements

Two-Pointer Method: Smallest Subarray with K Distinct Elements¶

https://tp-iiita.quora.com/The-Two-Pointer-Algorithm

In [1]:

# 
# Motivation Problem: Given an array containing N integers, you need to find the length 
# of the smallest contiguous subarray that contains at least K distinct elements in it. 
# Output "-1" if no such subarray exists.
#

def slide(arr,K):
    left = 0
    right = 0
    n = len(arr)
    ans = n+1 
    s = set()
    cnt = dict()
    
    while left < n:
        while right < n and len(s) < K:
            s.add(arr[right])
            if arr[right] in cnt.keys():
                cnt[arr[right]]=cnt[arr[right]]+1
            else:
                cnt[arr[right]]=1
            right+=1
            
        if len(s) >= K:
            ans = min(ans,right-left)
            
        if cnt[arr[left]]==1:
            s.remove(arr[left])
        
        cnt[arr[left]]-=1
        left+=1
    
    if (ans == len(arr)+1):
        ans = -1;
    return ans;       

        
test_list = [1,1,2,2,3,4,4,5,4,3,3]
distinct_target = 4
print(test_list)
print("Min subset with",distinct_target,"distinct values:",slide(test_list,distinct_target))

[1, 1, 2, 2, 3, 4, 4, 5, 4, 3, 3]
Min subset with 4 distinct values: 5