Contains Duplicate II — Last-Seen Index HashMap at FAANG

Problem Statement#

Given an integer array nums and integer k, return true if any duplicate values exist within index distance k.

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

Input:  nums = [1, 2, 3, 1], k = 3
Output: true

Input:  nums = [1, 0, 1, 1], k = 1
Output: true

Input:  nums = [1, 2, 3, 1, 2, 3], k = 2
Output: false

Why This Problem Matters#

LeetCode 219 Contains Duplicate II is a FAANG hashmap interview staple at Google, Amazon, Microsoft, and Meta. The interview signal is whether you choose the last-seen-index map (one pass, simple) or the size-k+1 HashSet sliding window (also one pass, sometimes faster constant factors).

The last-seen-index pattern reappears in Longest Substring Without Repeating Characters, Subarray with Distinct Elements, and many sliding-window questions. Hash table FAANG fluency includes both variants because they teach two distinct mental models: per-key history versus bounded membership.

In production, the same idea backs idempotency keys with TTL, deduplication windows in event pipelines, and rate-limit "last-hit" tracking.

The Core Insight#

For each element nums[i], check if its previous occurrence is within distance k. Maintain a HashMap from value to last-seen index. If i - last[nums[i]] <= k, return true. Otherwise update last[nums[i]] = i and continue.

Alternative: maintain a HashSet of the last k+1 values. Slide the window: add nums[i], then remove nums[i - k - 1] once the window exceeds k+1. If insertion fails because the value already exists, return true.

Visual Dry Run#

Input nums = [1, 2, 3, 1], k = 3:

Solution (Optimal)#

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

var containsNearbyDuplicate = function(nums, k) {
    const last = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (last.has(nums[i]) && i - last.get(nums[i]) <= k) {
            return true;
        }
        last.set(nums[i], i);
    }
    return false;
};

Time: O(n) one pass with O(1) hash ops. Space: O(min(n, k)) for the index map; bounded by either input size or window width.

Common Mistakes#

• Using a HashSet of seen values without indexes; cannot enforce the distance constraint.
• Forgetting to update last[nums[i]] = i after a non-match within the window.
• Off-by-one on i - last[x] <= k — the inclusive bound is <=, not <.
• Holding all indexes per value (a list) when only the most recent is needed.
• Using nums.indexOf in JavaScript (O(n) per call) instead of a Map.

Interview Tips#

• Mention both the last-seen-index map and the size-k+1 HashSet variants.
• Justify the inclusive bound when discussing distance.
• For very small k, the sliding-window HashSet has tighter memory; cite this trade-off.
• For large k, the HashMap variant uses less memory because not all values land in the window.

Follow-up Questions#

• Generalize to Contains Duplicate III (LC 220). (Hint: bucketize values by t+1 and check neighboring buckets.)
• What if nums is a stream? (Hint: TTL eviction on the HashMap.)
• How would you parallelize for huge arrays? (Hint: shard by value modulo p.)
• What if values are objects with custom hashing? (Hint: ensure the hash function is consistent.)
• Why is HashSet sliding window faster on very small k? (Hint: smaller working set, better cache locality.)

Key Takeaways#

• LeetCode 219 Contains Duplicate II uses a value-to-last-index HashMap.
• Return true the moment i - last[nums[i]] <= k.
• The size-k+1 HashSet sliding window is an equivalent O(n) alternative.
• Always update last[nums[i]] = i after the non-match check.
• Time is O(n); space is O(min(n, k)).
• The pattern reappears in Longest Substring Without Repeating Characters and event-stream dedup.
• Inclusive bound (<=) is critical; off-by-one is the most common bug.