#219
Contains Duplicate II
Easy Fixed window + HashSet
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether two equal values exist whose indexes are at most k apart.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: are there two equal values at most k apart?
Why this works: only the last k values matter. Keep them in a set and drop the one that falls out.
Example: [1, 2, 3, 1], k = 3
window {1, 2, 3}next 1 is already in the window → true
✦Hints open one at a time
Only the last k elements matter for the current index.
Keep them in a HashSet and drop the one that falls out of range.
↗Approach
Slide a window of size k as a set. If the current value is already in the set, return true. Add it, and remove nums[i - k] once the window is too big.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> window = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (!window.add(nums[i])) return true; // already inside the window
if (window.size() > k) window.remove(nums[i - k]);
}
return false;
}
}!Common mistake
Removing the old element before checking, with an off-by-one that makes the window k - 1 wide.
Complexity
- Time: O(n).
- Space: O(k).
Topic: Sliding Window
🎬 Episode 10: video coming soon