Contains Duplicate II: Sliding Window with a Hash Map

LeetCode Contains Duplicate II (#219) adds a twist to the classic duplicate detection problem. Instead of just asking "is there a duplicate?", it asks: given an integer array nums and an integer k, return true if there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) is at most k.

In other words, you need to find a duplicate, but the two occurrences must be close together. Close enough that their index difference does not exceed k.

This constraint changes the approach. A plain set is no longer enough. You need to either track where you last saw each value or maintain a sliding window of the most recent k elements.

Two approaches, one idea

Both approaches revolve around the same core idea: only look for duplicates within a range of k indices. They differ in how they enforce that constraint.

Approach 1: Hash map (value to last index)

The most natural extension of the original Contains Duplicate solution. Instead of a set that only tracks "have I seen this value?", you use a dictionary that maps each value to the most recent index where it appeared.

For each element at index i, check if the value is already in the dict. If it is, compute the distance between the current index and the stored index. If that distance is k or less, you found your answer. Otherwise, update the stored index to the current one and keep going.

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

This is clean, runs in O(n) time, and uses O(n) space in the worst case (when every element is unique).

Approach 2: Sliding window set

Instead of storing every value you have ever seen, you maintain a set that only contains the last k elements. As you scan forward, you add the current element to the set. If the set already contains that element, you have a duplicate within distance k. Once the set grows beyond size k, you remove the oldest element (the one at index i - k).

def containsNearbyDuplicate(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])
    return False

This also runs in O(n) time, but the space is O(min(n, k)). When k is small relative to the array size, this uses significantly less memory than the hash map approach.

Step-by-step walkthrough

Let's trace through the hash map approach with nums = [1, 2, 3, 1] and k = 3. We maintain a dictionary mapping each value to the index where we last saw it.

At step 4, we find that 1 was previously seen at index 0. The distance is 3 - 0 = 3, which equals k = 3. The condition abs(i - j) is at most k is satisfied, so we return true.

Complexity analysis

Both approaches make a single pass through the array with O(1) operations per element. The hash map stores every unique value it has ever seen, so its space scales with the number of distinct elements (at most n). The sliding window set caps its size at k, so it never uses more than O(k) space.

For most interview purposes, either solution is acceptable. If k is known to be small (say, constant), the sliding window approach is strictly better on space.

The building blocks

This problem breaks down into two reusable patterns that appear across many LeetCode problems:

1. Hash map last-seen tracking

You maintain a dictionary that maps values to the most recent index where they appeared. On each iteration, you check if the current value has been seen before and whether the distance constraint is satisfied. Then you update the stored index.

This same pattern appears in problems like Two Sum, where you store values and indices to find complements, and in cycle detection problems where you track visited states.

2. Sliding window with a set

You maintain a fixed-size window of recent elements using a set. Elements enter the set as you scan forward. Once the window exceeds size k, you evict the oldest element. This is the classic sliding window pattern applied to duplicate detection.

This technique shows up in Longest Substring Without Repeating Characters and many other substring and subarray problems.

Edge cases

Keep these in mind when coding your solution:

• k = 0: No two distinct indices can have a distance of 0, so the answer is always false. Both solutions handle this naturally since i - last_seen[num] will always be at least 1, and the window set will never grow past size 0.
• No duplicates at all: The algorithm scans the entire array without finding a match and returns false. Both approaches handle this cleanly.
• Duplicate exists but beyond distance k: For example, nums = [1, 2, 3, 1] with k = 2. The duplicate 1 appears at indices 0 and 3, but 3 - 0 = 3, which is greater than k = 2. The hash map approach updates the stored index and keeps going. The sliding window approach evicts the old 1 before the new one arrives.
• Array of length 1: Only one element means no pair of distinct indices exists. Return false.

From understanding to recall

Reading through this solution once gives you understanding. But when a similar pattern shows up in a harder problem next week, will you recognize it instantly? Will you remember whether to use a dict or a set, and how to enforce the distance constraint?

That is where spaced repetition comes in. CodeBricks breaks this problem into its atomic building blocks (hash map last-seen tracking, sliding window set management) and drills them independently at increasing intervals. After a few review cycles, the pattern fires automatically when you see a "nearby duplicate" or "within distance k" constraint.

Related posts

• Contains Duplicate - The simpler version of this problem. Master the basic set approach before adding the distance constraint.
• The Sliding Window Pattern - A deep dive into the sliding window technique used in approach 2.
• Hash Map Patterns - How hash maps power O(1) lookups across dozens of LeetCode problems, including this one.