Contains Duplicate II

In this approach, we are going to apply sliding window technique, using two pointers left and right, find if there is any duplicate element found within the window size of k ( i.e. right - left).

Implementation steps:

• First, we will create three variables left, right that we will use to adjust the window, and a HashSet, dups to check the duplicate of an element. Initialize left=0 and right=0, that is the beginning window size.
• Next, run a while loop until right pointer reaches end of array, and check:
  • If the difference between right and left pointers are greater than K: This means that we are going out of window size k, so remove left pointer element from dups to keep the window size within k, and also increment left pointer.
  • If the right pointer element is found in HashSet: return true, since a duplicate found within the window size of k.
  • Finally, add right pointer element to the dups and then increment right pointer.
• If there is no duplicate found, at the end return false.

import java.util.HashSet;

public class ContainsDuplicatesII {

    static boolean containsNearbyDuplicate(int[] nums, int k) {

        int left = 0;
        int right = 0;
        HashSet<Integer> dups = new HashSet<>();
        while(right < nums.length) {
            if(right-left > k) {
                dups.remove(nums[left]);
                left++;
            }
            if(dups.contains(nums[right])) {
                return true;
            }
            dups.add(nums[right]);
            right++;
        }
        return false; // if nothing found
    }

    public static void main(String[] args) {
        System.out.println(containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3));

    }
}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(k) for the HashSet that is used check duplicates, and at any given time it contains atmost k elements.