Contains Duplicate II

Detect any duplicate pair within index distance k using a sliding hash set.

Easy
Time O(n) Space O(k)
LeetCode
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 = 3true
  • nums = [1,0,1,1], k = 1true
  • nums = [1,2,3,1,2,3], k = 2false

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#

Contains Duplicate II
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.