Contains Duplicate II

How it works

We only need to check for duplicates within a sliding window of size k. Using a hash set, we maintain exactly the elements in the current window. If a new element already exists in the set, we found a duplicate within distance k. We slide the window by removing the leftmost element when the window exceeds size k.

Steps

1. Create an empty hash set to represent the sliding window.
2. Use two pointers L and R, with R iterating through the array.
3. If the window size R - L exceeds k, remove nums[L] from the set and increment L.
4. If nums[R] is already in the set, return true.
5. Add nums[R] to the set.
6. If no duplicate is found, return false.

Complexity

• Time complexity: O(n)
• Space complexity: O(min(n, k))

Where n is the size of the array nums and k is the maximum distance between two equal numbers.

Things to watch for

Off-by-One Error in Distance Check

The condition requires the distance to be "at most k", meaning abs(i - j) <= k, not < k. Using strict inequality will miss valid pairs that are exactly k positions apart.

Storing All Indices Instead of Most Recent

The hash map only needs to store the most recent index for each value. Storing all indices wastes memory and complicates the logic. Since we iterate left to right, we only care about the closest previous occurrence.

from typing import List

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        L = 0

        for R in range(len(nums)):
            if R - L > k:
                window.remove(nums[L])
                L += 1
            if nums[R] in window:
                return True
            window.add(nums[R])

        return False

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> window;
        int L = 0;

        for (int R = 0; R < nums.size(); R++) {
            if (R - L > k) {
                window.erase(nums[L]);
                L++;
            }
            if (window.find(nums[R]) != window.end()) {
                return true;
            }
            window.insert(nums[R]);
        }
        return false;
    }
};