Contains Duplicate II
Check whether two equal values sit at most k positions apart, with a sliding set that holds only the last k values.
Problem Understanding
Contains Duplicate II: return true if there are two different indices i and j with nums[i] == nums[j] and |i − j| ≤ k.
Examples: [1, 2, 3, 1] with k = 3 is true (the 1s are 3 apart); [1, 2, 3, 1, 2, 3] with k = 2 is false (every repeat is 3 apart).
The Intuition: Remember Only What Is Close Enough
Contains Duplicate keeps every value in a set. Here a match only counts if it is within k positions, so the set should hold only the last k values: a fixed-size sliding window.
- If
nums[i]is already in the set, a copy is at mostkback: returntrue. - Otherwise add it.
- If the set now has more than
kvalues, removenums[i − k], which is too far behind to matter again.
Each value is added and removed once, so the whole scan is O(n).
Interactive Walkthrough
The shaded cells are the values currently in the set: the k positions just before i. Watch old values fall out as i moves, and a repeat light up green when it is still inside the window.
Dry Run Table
Input: [1, 2, 3, 1, 2, 3], k = 2
| i | nums[i] | Set before | Action |
|---|---|---|---|
| 0..1 | 1, 2 | grows | add |
| 2 | 3 | {1, 2} | add, remove 1 |
| 3 | 1 | {2, 3} | add, remove 2 |
| 4 | 2 | {3, 1} | add, remove 3 |
| 5 | 3 | {1, 2} | add, remove 1 |
No repeat was ever in the set: false.
The Solution Template
A set of the last k values. The C snippet has no built-in set, so it looks back over up to k positions directly (O(n·k)).
Contains Duplicate II Code
1var containsNearbyDuplicate = function(nums, k) {2 const window = new Set();3 for (let i = 0; i < nums.length; i++) {4 if (window.has(nums[i])) return true;5 window.add(nums[i]);6 if (window.size > k) window.delete(nums[i - k]);7 }8 return false;9};
Edge Cases & Common Mistakes
- k = 0: the set is emptied straight away, so the answer is always false.
- k ≥ n: nothing is ever removed; it becomes plain Contains Duplicate.
- Removing nums[i − k − 1]: off by one; after adding nums[i], the value that just fell out of range is nums[i − k].
- Checking after adding: check membership first, or nums[i] will always find itself.
Summary
Keep the last k values in a set. A value already in the set has a copy at most k back: return true. Otherwise add it and remove the value that has fallen out of range. O(n) time, O(min(n, k)) space.
More practice: DSA interview questions with answers · patterns cheat sheet