Two Pointer Method: K Distinct Elements

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

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

---

/*
* 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.
*/

class kdistinct {

    static int slide(int[] arr, int K) {

        Set<Integer> s = new HashSet<Integer>();
        Map<Integer,Integer> cnt = new HashMap<Integer,Integer>();

        int left = 0;
        int right = 0;
        int ans = 9999;
        int n = arr.length;

        while (left < n) {
            while ( right < n && s.size() < K ) {
                s.add(arr[right]);
                if (cnt.get(arr[right])==null) {
                    cnt.put(arr[right],1);
                }  else {
                    cnt.put(arr[right],cnt.get(arr[right])+1);
                }
                right++;
            }

            if (s.size() >= K) {
                ans = Math.min(ans,right-left);
            }

            //System.out.println(cnt);
            //System.out.println(s);
            if ( cnt.get(arr[left])==1 ) s.remove(arr[left]);
            cnt.put(arr[left],cnt.get(arr[left])-1);
            left++;
        }
        if (ans == 9999) ans = -1;
        return ans;
    }

    public static void main(String args[]) {
        int arr1[] = { 1,1,2,2,3,4,4,5,4,3,3 };
        int K = 4;
        System.out.println(Arrays.toString(arr1));
        System.out.println("Min subset with "+K+" distinct values:  "+slide(arr1,K));
    }
}

---

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