Contains Duplicate II
Detect any duplicate pair within index distance k using a sliding hash set.
2 min read
hashing sliding-window
Problem#
Return true if there are two distinct indices i and j with nums[i] == nums[j] and |i - j| <= k.
Examples#
nums = [1,2,3,1], k = 3→truenums = [1,0,1,1], k = 1→truenums = [1,2,3,1,2,3], k = 2→false
Constraints#
1 <= nums.length <= 10^5,0 <= k <= 10^5.
Approach#
Maintain a hash set of the most recent k+1 elements. For each new element, check membership; if absent, insert and evict the element leaving the window.
Solution#
class Solution {public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> window; for (int i = 0; i < (int)nums.size(); ++i) { if (window.count(nums[i])) return true; window.insert(nums[i]); if ((int)window.size() > k) window.erase(nums[i - k]); } return false; }};func containsNearbyDuplicate(nums []int, k int) bool { window := map[int]bool{} for i, v := range nums { if window[v] { return true } window[v] = true if len(window) > k { delete(window, nums[i-k]) } } return false}from typing import List
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: window = set() for i, v in enumerate(nums): if v in window: return True window.add(v) if len(window) > k: window.remove(nums[i - k]) return Falsefunction containsNearbyDuplicate(nums, k) { const window = new Set(); for (let i = 0; i < nums.length; i++) { if (window.has(nums[i])) return true; window.add(nums[i]); if (window.size > k) window.delete(nums[i - k]); } return false;}class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> window = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (window.contains(nums[i])) return true; window.add(nums[i]); if (window.size() > k) window.remove(nums[i - k]); } return false; }}function containsNearbyDuplicate(nums: number[], k: number): boolean { const window = new Set<number>(); for (let i = 0; i < nums.length; i++) { if (window.has(nums[i])) return true; window.add(nums[i]); if (window.size > k) window.delete(nums[i - k]); } return false;}Editorial#
The sliding set guarantees we only check pairs within distance k. Removing the element that just left the window keeps the set’s size bounded by k, so each lookup is O(1) amortized.
Complexity#
- Time: O(n).
- Space: O(k).
Concept revision#
Related#