Contains Duplicate II

Contains Duplicate II

What is this problem about?

The Contains Duplicate II interview question adds a distance constraint to the duplicate detection. You need to return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Why is this asked in interviews?

This Contains Duplicate II coding problem is asked by companies like Meta and Apple to see if a candidate can implement a Sliding Window efficiently. It evaluates how you manage a dynamic collection of data (the window) while processing a stream of inputs.

Algorithmic pattern used

This utilizes the Array, Hash Table, Sliding Window interview pattern.

1. Maintain a Hash Set of size at most k.
2. As you iterate through the array:
   • If the current number is in the set, you've found a duplicate within distance k.
   • Add the current number to the set.
   • If the set size exceeds k, remove the element that is outside the current window (nums[i-k]).

Example explanation

Array: [1, 2, 3, 1], k = 3

1. Set: {1}
2. Set: {1, 2}
3. Set: {1, 2, 3}
4. Current: 1. Is 1 in set? Yes! Return true. If k = 2, the 1 would have been removed from the set before we reached the duplicate at index 3.

Common mistakes candidates make

• Storing indices in a map: Storing every index for every number, which uses O(N) space regardless of k. The sliding window set approach uses O(min(N, k)) space.
• Off-by-one errors: Removing elements from the set at the wrong time (e.g., at i-k-1 instead of i-k).
• Inefficient removal: Using an array instead of a set for the window, leading to O(K) removal time.

Interview preparation tip

Whenever a problem involves a constraint like "within distance k" or "in a window of size k," think about how to maintain a Set or Map that only contains the elements currently in that window.