Contains Duplicate II
Easy· fixed window· hash set
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Return true if two different indices i and j hold the same value and are at most k apart, that is |i - j| <= k.
Examples
Input: nums = [1,2,3,1], k = 3
Output: true
The two 1s are exactly 3 positions apart.
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Constraints
- • 1 <= nums.length <= 10^5
- • 0 <= k <= 10^5
Hints & approach
Hint 1
You only care about the last k elements before the current one.
Hint 2
Keep those elements in a set that slides along with you.
Approachtry the hints first
Maintain a hash set containing the values in the window of the last k indices. For each index i, if nums[i] is already in the set, a close duplicate exists, so return true. Otherwise add nums[i], and if the set now covers more than k elements, remove nums[i - k]. If the loop finishes, no qualifying pair exists.
Time O(n) · Space O(min(n, k))
