Contains Duplicate II
Understanding the Problem
We need to determine whether any value appears at least twice within a window of size k. Put differently, for any element at index i, we want to know if the same value appeared at any index j where i - k <= j < i.
The original Contains Duplicate problem asks whether duplicates exist anywhere in the array. This version adds a proximity constraint, and that changes what we need to remember. Instead of tracking every element seen so far, we only need to track the elements in the current window of size k.
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, O(n^2) brute force might be too slow in the worst case, but O(n * min(n, k)) could pass depending on k. We should aim for O(n).-10^9 <= nums[i] <= 10^9→ Values range widely, so using values as array indices isn't feasible. We need a hash-based approach.0 <= k <= 10^5→ k can be as large as the array itself, so in the worst case the window is the entire array.
Approach 1: Brute Force
Intuition
Compare each element against the k elements before it. If any of them match, return true. If we scan the entire array without finding a match, return false.
This translates the problem statement directly into code. For each index i, we check every index j from max(0, i - k) up to i - 1.
Algorithm
- Iterate through each index
ifrom 0 ton - 1 - For each
i, iterate through indicesjfrommax(0, i - k)up toi - 1 - If
nums[i] == nums[j], returntrue - If no duplicate pair is found after checking all elements, return
false
Example Walkthrough
Code
- Time Complexity: O(n * min(n, k)). For each of the n elements, we check up to min(n, k) previous elements. When k is small, this is fast. When k approaches n, it degrades to O(n^2).
- Space Complexity: O(1). We only use a few variables for loop indices. No additional data structures needed.
Each element triggers a scan of up to k previous elements. Storing each value's most recent index in a hash map replaces that scan with a single O(1) lookup.
Approach 2: Hash Map (Last Seen Index)
Intuition
Instead of looking backward from each element, we can flip the perspective. As we scan forward through the array, we keep a hash map that records the most recent index where each value appeared. When we encounter a value that's already in the map, we check whether the stored index is within distance k of the current index.
Only the most recent index matters. If a value appeared at indices 2, 7, and 15, and we're currently at index 17 with k = 3, we only need to check against index 15. If index 15 isn't close enough, indices 2 and 7 are farther away and can't be either. Overwriting the map entry on every occurrence keeps the comparison distance as tight as possible.
Algorithm
- Create a hash map to store each value's most recent index
- Iterate through the array with index
i - If
nums[i]is already in the map andi - map.get(nums[i]) <= k, returntrue - Update the map with
nums[i] -> i(overwriting any previous index) - If we finish the loop without finding a match, return
false
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once. Each hash map lookup and insertion is O(1) on average.
- Space Complexity: O(n). In the worst case (all unique elements), the map stores every element in the array.
The hash map approach runs in O(n) time, but the map can grow to hold all n elements even though only the last k matter. The next approach caps the data structure at k elements.
Approach 3: Sliding Window with Hash Set
Intuition
Maintain a hash set that contains exactly the elements in a window of size k. As we move through the array, we add the current element to the set. If it's already there, we found a nearby duplicate. If the set grows beyond size k, we remove the oldest element, the one that fell out of the window.
This is the sliding window pattern. The window holds the k elements before the current index, and the set gives us O(1) membership checks within that window.
Algorithm
- Create an empty hash set
- Iterate through the array with index
i - If
nums[i]is already in the set, returntrue(duplicate within window) - Add
nums[i]to the set - If the set size exceeds
k, removenums[i - k](the element leaving the window) - If we finish without finding a duplicate, return
false
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once. Each set operation (contains, add, remove) is O(1) on average.
- Space Complexity: O(min(n, k)). The set never holds more than k + 1 elements. If k >= n, the set holds at most n elements.