Contains Duplicate II

Problem

Given an integer array nums and an integer k, decide whether the array contains two distinct indices i and j such that nums[i] == nums[j] and the indices are close together: abs(i - j) <= k. Return True if such a pair exists, False otherwise.

In other words: does any value repeat within a window of k + 1 consecutive positions?

Examples

• nums = [1, 2, 3, 1], k = 3 → True — the two 1s sit at indices 0 and 3, and 3 - 0 = 3 <= k.
• nums = [1, 0, 1, 1], k = 1 → True — the 1s at indices 2 and 3 are adjacent.
• nums = [1, 2, 3, 1, 2, 3], k = 2 → False — every repeated value is exactly 3 apart, which exceeds k = 2.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

Both n and k can be 10^5, so an O(n·k) scan of each index’s neighborhood can hit 10^10 steps — the expected solution is linear.

Think about it first

TL;DR

Fixed-size sliding window backed by a hash set — O(n) time, O(min(n, k)) space.

Approach 1 — Brute force

For each index, look back at (up to) the previous k elements.

def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(max(0, i - k), i):
            if nums[j] == nums[i]:
                return True
    return False

Complexity: O(n·k) time, O(1) space. With n = k = 10^5 this is about 10^10 comparisons, too slow.

Approach 2 — Sliding window of the last k values

The condition “an equal value within distance k” only concerns the window of the previous k elements, and that window slides forward one element at a time: one value enters, one leaves. A hash set can hold the window’s contents, turning the inner O(k) scan into an O(1) membership test. The window never moves backward, so total work is linear.

def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
    window: set[int] = set()
    for i, x in enumerate(nums):
        if x in window:
            return True
        window.add(x)
        if len(window) > k:          # window spans k+1 indices; evict the oldest
            window.remove(nums[i - k])
    return False

Walkthrough on nums = [1, 2, 3, 1], k = 3:

The set never exceeds k = 3 entries, so no eviction happens before the duplicate is found.

The False case, nums = [1, 2, 3, 1, 2, 3], k = 2, shows the eviction step. At i = 2, adding 3 grows the set to {1, 2, 3} (size 3 > k), so nums[0] = 1 is evicted. Entering i = 3 the set is {2, 3}: the incoming 1 finds no match, which is correct because the old 1 sits at distance 3 > k. The same shift repeats for 2 and 3, and the loop ends with False. Eviction runs at the end of each iteration so that stale, too-far elements are gone before the next membership check.

Complexity: O(n) time; O(min(n, k)) space for the set.

Approach 3 — Last-seen index map

You don’t need the whole window. For each value, only its most recent occurrence can be within distance k of the current index; any older occurrence is farther away.

def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
    last_seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        if x in last_seen and i - last_seen[x] <= k:
            return True
        last_seen[x] = i
    return False

Complexity: O(n) time, O(n) space in the worst case (all values distinct). Slightly more memory than Approach 2 when k is small, but no eviction logic.

Common pitfalls

• Window size off-by-one: abs(i - j) <= k means the window covers k + 1 indices. Keeping the set at at most k values (evicting when it exceeds k) is the correct invariant — evicting at k + 1 values lets a distance-k+1 pair slip through as a false positive.
• Evicting before checking. Check membership first, then insert, then evict; reordering can either miss a valid pair or match an element that already slid out.
• k = 0 edge case: distance must be at least 1 between distinct indices, so the answer is always False; both solutions handle it naturally (the set stays empty / distance i - last is never <= 0).

Pattern takeaway

This is the fixed-size form of sliding window: the window’s width is set by the problem (k + 1 indices), so there’s no grow or shrink decision, just add the entering element and drop the leaving one. The reusable idea is pairing the window with a hash structure that summarizes its contents, so a question you would otherwise answer by rescanning the window becomes an O(1) lookup.