Contains Duplicate II

Many real checks are about repeats that happen close together. A fraud rule flags the same card used twice within 5 transactions. A log monitor alerts when the same error ID shows up twice within 100 lines. A repeat far apart is fine; a repeat nearby is the signal.

This lesson starts from the simplest hash-set problem, "is there any repeat at all?", and adds a distance limit. The distance turns the seen-set into an index map, and shows the check-then-record rhythm that every problem in this section uses.

The problem

You are given a list of integers numbers and an integer k ≥ 0. Return True if there are two different positions i and j with numbers[i] == numbers[j] and |i − j| ≤ k. Otherwise return False.

• numbers = [5, 6, 7, 5, 6, 6], k = 2 → True. The two 6s at positions 4 and 5 are 1 apart. (The 5s are 3 apart, too far.)
• numbers = [1, 2, 3, 1, 2, 3], k = 2 → False. Every repeat is exactly 3 apart.

Constraints: n ≤ 10⁵, 0 ≤ k ≤ 10⁵, values between −10⁹ and 10⁹.

Warm-up: any duplicate at all. Without the distance limit this is the seen-set template from the core lesson: walk the list, return True if the value is already in the set, otherwise add it. O(n) time, O(n) space. Keep it in mind — the problem below is the same loop with one change.

Clarifying questions

• Is the distance limit inclusive? Yes: |i − j| ≤ k. Positions exactly k apart count.
• What if k = 0? Two different positions are always at least 1 apart, so the answer is always False.
• What if k is larger than the list? Then any duplicate at all counts, and this becomes the warm-up problem.
• Empty list or one element? False — there is no pair.

Approach 1: compare each value with its next k neighbours

For each position i, look at positions i + 1 to i + k (stopping at the end) and return True on any equal value.

1def contains_nearby_duplicate_brute(numbers: list[int], k: int) -> bool:2    """Compare each value with the next k values. O(n * k) time."""3    for i in range(len(numbers)):4        for j in range(i + 1, min(i + k, len(numbers) - 1) + 1):5            if numbers[i] == numbers[j]:6                return True7    return False

Time: O(n · min(n, k)). Space: O(1).

When k is small, say 3, this is fine: about 3n comparisons. The problem is that k can be as large as n. With n = k = 10⁵ it is about 5 × 10⁹ comparisons — the same wall as Two Sum's brute force. And again the inner loop is a search: "is my value among the next k?"

The key insight

Stand at position j and look left. There may be many earlier copies of numbers[j]. Which one should you compare against?

Only the most recent one. It is the closest copy to j, so if even it is more than k away, every older copy is farther still. And if it is within k, you are done. So you never need a list of past positions — one index per value is enough, and it should always be the latest index.

That gives an index map: key = value, value = the last position it was seen. At each step, check the stored index, then overwrite it with the current one. Overwriting is not a loss of information; it is throwing away positions that can never matter again.

There is a second way to see the same fact. At position j, only the values at positions j − k to j − 1 can pair with it. That is a window of the last k values. Keep exactly those in a set and the question becomes the plain seen-set question, restricted to the window. This gives Approach 3.

Approach 2: index map of latest positions

1def contains_nearby_duplicate(numbers: list[int], k: int) -> bool:2    """Index map: remember the latest index of every value."""3    last_index: dict[int, int] = {}4    for index, value in enumerate(numbers):5        if value in last_index and index - last_index[value] <= k:6            return True7        last_index[value] = index        # the newest index is always the best one8    return False

The check reads the old index; only then is it replaced. Dry run on [5, 6, 7, 5, 6, 6], k = 2:

At index 3 the 5 is found, but 3 steps back. The map is updated to 3 anyway, because from now on position 3 is the only 5 that could matter. The same happens to 6 at index 4, which is what lets index 5 find a gap of 1.

Time: O(n) on average — one lookup and one write per element. Space: O(n) in the worst case, when all values are distinct.

Approach 3: a sliding set of the last k values

If the list is huge and k is small (a stream of millions of events, k = 100), an O(n) map is wasteful. Keep only the last k values.

1def contains_nearby_duplicate_window(numbers: list[int], k: int) -> bool:2    """Sliding set: hold only the last k values."""3    window: set[int] = set()4    for index, value in enumerate(numbers):5        if value in window:6            return True7        window.add(value)8        if len(window) > k:              # window now covers k + 1 indices9            window.remove(numbers[index - k])10    return False

After adding the current value, the set covers positions index − k to index, which is one too many. Removing numbers[index − k] leaves exactly the k values that the next element may pair with. Because the function returns at the first duplicate, the set never holds two copies of a value, so its size really is the number of positions it covers.

Dry run on the same input:

Time: O(n). Space: O(min(n, k)). Same speed as Approach 2, and memory bounded by k instead of n — which also makes it work on an endless stream.

Edge cases

• k = 0: Approach 2 finds gaps of at least 1, never ≤ 0, so returns False. Approach 3 adds each value and immediately removes it, so the set stays empty. Both correct with no special case.
• k ≥ n: Approach 3 never removes anything and becomes the plain seen-set.
• Empty or single-element list: the loop finds nothing and returns False.
• A value that repeats many times: [1, 0, 1, 1], k = 1. The first repeat (positions 0 and 2) is too far, but positions 2 and 3 are 1 apart. This only works because the map was updated to 2.

Follow-ups

• Values that are close, not equal (often called Contains Duplicate III): return True if |numbers[i] − numbers[j]| ≤ t and |i − j| ≤ k. Put each value in a bucket value // (t + 1) and keep a map from bucket to value for the last k positions; a match can only be in the same bucket or one of its two neighbours. Still O(n).
• Return the positions, not a boolean: return [last_index[value], index] at the moment the check succeeds.
• The input is an endless stream: use Approach 3. Its memory is O(k) no matter how long the stream runs.