219. Contains Duplicate II

This question on LeetCode is good practice for sliding window problems. Of course, we can solve it easily using a collections Map, but it's interesting and efficient to apply the sliding window algorithm to tackle it.

Question

Solution

HashMap

// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            int n = nums[i];
            if(map.containsKey(n) && i-map.get(n) <= k) {
                return true;
            }
            map.put(n, i);
        }

        return false;
    }
}

Slide Window

We can follow the diagram I created below step by step.

// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            // Step 1: Check if there is duplicate among the set
            if(!set.add(nums[i])) {
                return true;
            }
            // Step 2: Remove the first element in the set
            if(set.size()>k) {
                set.remove(nums[i-k]);
            }
        }

        return false;
    }
}