LeetCode 219 – Contains Duplicate II

Contains Duplicate with a distance limit, and the limit is what turns a set into a sliding window. The change is two lines, and the reason it works is worth saying: a set that only ever holds the last k elements answers "is there a duplicate nearby" with the same lookup that answered "is there a duplicate at all".

The problem

Return true if there are two distinct indices i and j with nums[i] == nums[j] and |i − j| ≤ k.

[1,2,3,1],     k = 3  -> true    indices 0 and 3, distance 3
[1,0,1,1],     k = 1  -> true    indices 2 and 3
[1,2,3,1,2,3], k = 2  -> false   every repeat is 3 apart
[1,2,3,1],     k = 0  -> false   distance 0 needs i == j, which is not allowed
[99],          k = 1  -> false

k = 0 is the boundary to check: the indices must be distinct, so no pair can have distance 0 and the answer is always false.

Two framings, same code

As a window. Keep a set of the last k values. At index i, the set holds exactly nums[i−k … i−1], so a hit means a duplicate within k. After checking, add nums[i] and evict nums[i−k] if it has fallen out of range.

As a last-seen map. Store value → most recent index. On seeing a value already present, compare the indices. Then overwrite with the current index — because a closer occurrence is strictly better for every future check, so the older one is never needed again.

Both are O(n). The window is tighter in space when k is much smaller than the number of distinct values; the map is simpler and is what most people write. That "the most recent index is always the useful one" observation is the map version's whole justification, and it is worth stating.

Java

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // The set holds exactly the previous k values -- nothing further back.
        Set<Integer> window = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            // A hit means a duplicate within k, because that is all the set contains.
            if (!window.add(nums[i])) return true;

            if (window.size() > k) {
                window.remove(nums[i - k]);   // this one is now out of range
            }
        }

        return false;
    }
}

window.size() > k rather than i >= k. They agree while the values are distinct, and once a duplicate is found the method has already returned — so either works here. Sizing off the set states the invariant directly: never hold more than k.

k = 0 makes the set empty after every iteration, so nothing is ever found. That falls out rather than needing a guard, which is worth tracing rather than assuming.

add returning false is the same one-hash idiom as problem 217.

Python

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

        for i, num in enumerate(nums):
            if num in window:
                return True

            window.add(num)

            if len(window) > k:
                window.discard(nums[i - k])   # discard, not remove: never raises

        return False

discard rather than remove: remove raises KeyError if the value is absent, and it can be absent when the array holds duplicates that were already evicted. discard is the total function, and reaching for it here is a small correctness choice rather than a style one.

The last-seen map version

    def containsNearbyDuplicateMap(self, nums: list[int], k: int) -> bool:
        last_seen: dict[int, int] = {}

        for i, num in enumerate(nums):
            if num in last_seen and i - last_seen[num] <= k:
                return True

            last_seen[num] = i        # a closer occurrence is always better

        return False

Overwriting unconditionally is the part to explain. Keeping the earlier index could only produce a larger distance for every future comparison, so it can never help — the most recent occurrence dominates.

Its space is the number of distinct values rather than k, which is worse when k is small and better when the array is mostly repeats.

Complexity

Approach	Time	Space
Sliding-window set	`O(n)`	`O(min(n, k))`
Last-seen map	`O(n)`	`O(distinct values)`
Check every pair within k	`O(n · k)`	`O(1)`

One pass, one hash operation per element. The brute force is worth mentioning because it is fine when k is tiny — k = 1 makes it a single adjacent-pair scan in constant space, which beats both.

Where the family stops being easy

Contains Duplicate III (220) adds a value tolerance: find i, j with |i − j| ≤ k and |nums[i] − nums[j]| ≤ t. A hash set cannot answer "is there a nearby value close to this one" — that needs an ordered structure with a range query, so the window becomes a TreeSet and the lookup becomes floor/ceiling, or a bucketing scheme that makes it O(n).

That is the real lesson of the trio: exact match is a hash problem, nearness is an ordering problem, and swapping the structure is what the third variant is testing.

What the interviewer is checking

That the set is bounded to k, so a hit implies proximity.
That the eviction index is i − k.
k = 0 returning false, without a special case.
That the last-seen map may overwrite, and why the older index is useless.
discard over remove in Python.
Empty array, single element, and k larger than the array.
That the value-tolerance variant needs an ordered structure.