Contains Duplicate II

Problem Description

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Examples

Constraints

• 1 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹
• 0 <= k <= 10⁵

Sliding Window Hash Set

Instead of storing the index of every element in a hash map, we can maintain a sliding window of size k using a hash set. As we iterate through the array, if the current element is already in the set, we found a duplicate within distance k and return true. We then add the current element to the set. If the set’s size exceeds k, we remove the oldest element (at index i - k) to maintain the window size. This ensures the set only contains elements within the distance constraint, optimizing space.

Solution 1: Sliding Window Set

Use a hash set to represent a sliding window of max size k.

import java.util.HashSet;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]); // slide window
            }
        }
        return false;
    }
}

class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        window = set()
        for i, num in enumerate(nums):
            if num in window:
                return True
            window.add(num)
            if len(window) > k:
                window.remove(nums[i - k])  # slide window
        return False

#include <vector>
#include <unordered_set>

class Solution {
public:
    bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
        std::unordered_set<int> window;
        for (int i = 0; i < nums.size(); i++) {
            if (window.count(nums[i])) {
                return true;
            }
            window.insert(nums[i]);
            if (window.size() > k) {
                window.erase(nums[i - k]); // slide window
            }
        }
        return false;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the array once and perform O(1) average lookup/insert operations.
• Space Complexity: O(min(n, k)) auxiliary space to store elements in the sliding window hash set.

Where It Breaks

If the lookup cost of elements is high (e.g. hashing large custom objects), the hash set insertions become a bottleneck. Since elements are simple integers here, lookups remain fast.

Common Mistakes

• Incorrect slide index: Removing nums[i - k - 1] instead of nums[i - k]. The sliding check must trigger when the set size exceeds k.
• Using a full hash map unnecessarily: Storing all indices in a hash map works but uses O(n) space instead of the optimized O(k) sliding window set space.

Frequently Asked Questions

Why remove elements when set size exceeds k? Removing the element at i - k ensures that any element remaining in the set is at most k positions away from the next index i + 1.

What if k is larger than the array length? The set size will never exceed k, so no elements will be removed, and the algorithm behaves like a normal duplicate detector.

← All Problems