Contains Duplicate II
Problem
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
- 1 ≤ nums.length ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
- 0 ≤ k ≤ 10⁵
Example
nums = [1,2,3,1], k = 3trueThe algorithm scans the array while tracking the last seen index of each number. At index 0, number 1 is stored with index 0. At index 3, the number 1 appears again. The difference between indices 3 and 0 is 3, which is within the allowed distance k=3, so the function returns true immediately. This early detection avoids unnecessary scanning of the entire array.
Approach
Straightforward Solution
A naive approach would compare every pair of elements within distance k, resulting in O(n*k) time complexity, which is too slow for large inputs.
Core Observation
The problem requires detecting duplicates within a sliding window of size k. The key is to efficiently track the most recent occurrence of each number and check if the current occurrence is close enough to the previous one.
Path to Optimal
The insight is to use a hash map to store the last index where each number appeared. As we iterate through nums, for each number, we check if it has been seen before and if the difference between the current index and the stored index is at most k. This reduces the time complexity to O(n) by avoiding redundant comparisons.
Optimal Approach
Iterate through nums once, maintaining a hash map from number to its last seen index. For each number, if it exists in the map and the index difference is at most k, return true immediately. Otherwise, update the map with the current index. If no such pair is found, return false after the loop.
Time
O(n)
Each element is processed once, and hash map lookups and updates are O(1) on average, resulting in linear time complexity.
Space
O(n)
In the worst case, all elements are distinct and stored in the hash map, requiring space proportional to the input size.
Pattern Spotlight
Hash Maps (Index Tracking for Duplicate Detection)
When needing to detect duplicates within a fixed index distance, use a hash map to remember the last occurrence of each element and check the distance on-the-fly to achieve O(n) time.
Solution
| 1 | class Solution: |
| 2 | def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: |
| 3 | |
| 4 | last_seen = {} |
| 5 | |
| 6 | for i, n in enumerate(nums): |
| 7 | |
| 8 | if n in last_seen and i - last_seen[n] <= k: |
| 9 | return True |
| 10 | |
| 11 | last_seen[n] = i |
| 12 | |
| 13 | return False |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public boolean containsNearbyDuplicate(int[] nums, int k) { |
| 6 | Map<Integer, Integer> lastSeen = new HashMap<>(); |
| 7 | for (int i = 0; i < nums.length; i++) { |
| 8 | int n = nums[i]; |
| 9 | if (lastSeen.containsKey(n) && i - lastSeen.get(n) <= k) { |
| 10 | return true; |
| 11 | } |
| 12 | lastSeen.put(n, i); |
| 13 | } |
| 14 | return false; |
| 15 | } |
| 16 | } |
| 1 | #include <unordered_map> |
| 2 | #include <vector> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | bool containsNearbyDuplicate(vector<int>& nums, int k) { |
| 9 | unordered_map<int, int> lastSeen; |
| 10 | for (int i = 0; i < (int)nums.size(); i++) { |
| 11 | int n = nums[i]; |
| 12 | if (lastSeen.count(n) && i - lastSeen[n] <= k) { |
| 13 | return true; |
| 14 | } |
| 15 | lastSeen[n] = i; |
| 16 | } |
| 17 | return false; |
| 18 | } |
| 19 | }; |
| 1 | var containsNearbyDuplicate = function(nums, k) { |
| 2 | const lastSeen = new Map(); |
| 3 | for (let i = 0; i < nums.length; i++) { |
| 4 | const n = nums[i]; |
| 5 | if (lastSeen.has(n) && i - lastSeen.get(n) <= k) { |
| 6 | return true; |
| 7 | } |
| 8 | lastSeen.set(n, i); |
| 9 | } |
| 10 | return false; |
| 11 | }; |
Step-by-Step Solution
Track Last Seen Indices of Numbers Using a Hash Map
| 4 | last_seen = {} |
Objective
To maintain a mapping from each number to its most recent index in the array.
Key Insight
By storing the last seen index of each number, the algorithm can instantly check if a newly encountered duplicate is within the allowed distance k. This transforms the problem from a costly pairwise comparison to a constant-time lookup per element, enabling a single-pass O(n) solution.
Interview Quick-Check
Core Logic
The hash map stores numbers as keys and their last seen indices as values, enabling O(1) average-time distance checks.
Common Pitfalls & Bugs
Failing to update the last seen index after checking can cause incorrect results by using stale indices.
Iterate Through Array and Detect Nearby Duplicates
| 6 | for i, n in enumerate(nums): |
| 8 | if n in last_seen and i - last_seen[n] <= k: |
| 9 | return True |
Objective
To scan the array, checking for duplicates within distance k and returning true immediately upon detection.
Key Insight
The algorithm leverages the hash map to check if the current number has appeared before and if the previous occurrence is close enough. This immediate check and early return prevent unnecessary processing, making the solution efficient and straightforward.
Interview Quick-Check
Core Logic
For each number, check if it exists in the map and if the index difference is at most k; if so, return true immediately.
State & Boundaries
The loop iterates over all indices and values, ensuring every element is checked exactly once.
Common Pitfalls & Bugs
Not checking the index difference or returning false prematurely can lead to incorrect answers.
Update the Last Seen Index
| 11 | last_seen[n] = i |
Objective
Record the current index of the number for future comparisons.
Key Insight
Updating the stored index ensures that the hash map always reflects the most recent occurrence, which produces correct distance checks for subsequent elements.
Interview Quick-Check
Core Logic
The map must store the most recent index of each number to maintain accurate distance calculations.
Common Pitfalls & Bugs
Failing to update this value can lead to stale index comparisons.
Return False When No Nearby Duplicates Are Found
| 13 | return False |
Objective
To conclude the function by returning false if no duplicates within distance k are detected after full iteration.
Key Insight
If the loop completes without returning true, it means no pair of duplicates satisfies the distance constraint. Returning false explicitly signals this outcome, completing the contract of the function.
Interview Quick-Check
Core Logic
Returning false after the loop confirms that no valid duplicate pairs exist within the specified distance.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if n in last_seen and i - last_seen[n] <= k:Check if the current number has been seen before and if the index difference is within k.
This conditional is the core correctness check that ensures duplicates are only considered if they are close enough, directly implementing the problem's requirement.
last_seen[n] = iUpdate the last seen index of the current number.
Updating the index ensures that the hash map always reflects the most recent occurrence, which is critical for accurate distance checks in subsequent iterations.
last_seen = {}Initialize a hash map to store the last seen index of each number.
This data structure is essential for achieving O(1) average-time lookups to check if a number has appeared recently, enabling the linear time solution.
return TrueReturn true immediately upon finding a valid nearby duplicate.
Early termination upon detecting a valid pair improves efficiency by avoiding unnecessary further scanning.
return FalseReturn false if no nearby duplicates are found after full iteration.
This line correctly signals that the array contains no duplicates within the specified distance, fulfilling the function's contract.
for i, n in enumerate(nums):Iterate through the array with index and value.
Enumerating both index and value is necessary to check the distance between duplicate occurrences and update the hash map accordingly.
Test Your Understanding
Why is it necessary to check the index difference before returning true when a duplicate is found?
Because the problem requires duplicates to be within distance k; duplicates farther apart do not satisfy the condition and must not cause an early return.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Contains Duplicate II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Contains Duplicate II drill