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.

class Solution:
    def containsNearbyDuplicate(self, 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 — hopeless.

Approach 2 — Sliding window of the last k values

The insight: the condition “some equal value within distance k” only ever 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 mirror the window’s contents, turning the inner O(k) scan into an O(1) membership test. The window never needs to move backward, so total pointer movement is linear.

class Solution:
    def containsNearbyDuplicate(self, 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.

Now the False case, nums = [1, 2, 3, 1, 2, 3], k = 2 — this is where eviction earns its keep. At i = 2, adding 3 grows the set to {1, 2, 3} (size 3 > k), so nums[0] = 1 is evicted immediately. Entering i = 3 the set is {2, 3}: the incoming 1 finds no match — 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 precisely 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

The insight: 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).

class Solution:
    def containsNearbyDuplicate(self, 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 flavor of sliding window: the window’s width is dictated by the problem (k + 1 indices), so there’s no grow/shrink decision — just “add the entering element, drop the leaving one.” The reusable trick is pairing the window with a hash structure that summarizes its contents, so the question you’d naively answer by rescanning the window becomes an O(1) lookup.