Contains Duplicate II

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Solution

HashMap: O(n) time, O(n) space

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length < 2) return false;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num) && i - map.get(num) <= k) return true; //i is always > than value in map
            map.put(num, i);
        }
        return false;
    }
}

Sliding Window with Set: O(n) time, O(n) space

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length < 2) return false;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k) set.remove(nums[i - k - 1]);
            if (!set.add(nums[i])) return true;
        }
        return false;
    }
}

Analysis

The HashMap solution is very general
The Set solution is more interesting, and it kind of uses Sliding Window
We know the duplicated elements' indices must have difference at most k
Hence, as long as we reach further than distance k, we remove the first element
which is nums[i - k - 1] from the set
Then we simply check if we can add current element into our set
If not, we know we have qualified elements