Contains Duplicate II
Asked at Google, Netflix
Problem
Given an integer array and an integer k, determine if there are two distinct indices i and j such that nums[i] == nums[j] and the absolute difference between i and j is at most k. This is a sliding window problem with hash map tracking.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Netflix | Easy | View all Netflix questions → |
How to Think About It
Brute force: for each element, check the next k elements for a duplicate. That's O(n * k). Too slow for large k.
Better: use a hash set as a sliding window of size k. For each element, check if it's in the set. If yes, return true. Then add the element. If the window exceeds size k, remove the oldest element. O(n) time, O(k) space.
Optimal: use a hash map storing the last seen index of each element. For each element, if it's in the map and the stored index is at least i - k, return true. Update the stored index. O(n) time, O(n) space.
Visual walkthrough for [1,2,3,1], k=3:
Map: {}
i=0, num=1: not in map. Map: {1:0}
i=1, num=2: not in map. Map: {1:0, 2:1}
i=2, num=3: not in map. Map: {1:0, 2:1, 3:2}
i=3, num=1: in map at index 0. 3 - 0 = 3 <= k=3. Return true!
Visual walkthrough for [1,2,3,1,2,3], k=2:
Map: {}
i=0, num=1: Map: {1:0}
i=1, num=2: Map: {1:0, 2:1}
i=2, num=3: Map: {1:0, 2:1, 3:2}
i=3, num=1: in map at 0. 3-0=3 > k=2. Update Map: {1:3, 2:1, 3:2}
i=4, num=2: in map at 1. 4-1=3 > k=2. Update Map: {1:3, 2:4, 3:2}
i=5, num=3: in map at 2. 5-2=3 > k=2. Update Map: {1:3, 2:4, 3:5}
No match found. Return false.
Edge cases: k=0 (no valid pair since i != j), single element (return false), all elements same (return true if k >= 1).
Optimal Approach
Use a hash map storing each element's last seen index. For each element at index i:
- If the element is in the map and
i - map[element]<= k, return true. - Update
map[element] = i.
The map naturally handles the k-distance constraint: if the stored index is too far back (> k), it won't satisfy the condition. Updating to the latest index ensures future comparisons use the closest match.
Time: O(n) -- single pass. Space: O(n) for the hash map.
What Trips People Up in Real Interviews
Using a sliding window hash set instead of a hash map. A set tells you IF the element is in the window but not WHERE. You need the index to check the distance constraint.
Forgetting that the stored index might be outside the k-distance window. If i - seen[num] > k, it's a valid duplicate but too far apart. Update the stored index to the current one.
Confusing absolute difference with exact difference. The problem says abs(i - j) <= k, which means the distance in either direction. Since we iterate left to right, we only need to check if i - seen[num] <= k.
Not updating the stored index. If you keep the first occurrence, a later duplicate might falsely match against a distant first occurrence. Always update to the latest index.
Returning true when k=0. With k=0, the only pair is (i, i) which is not two distinct indices. Return false for k=0.
Solution Code
def containsNearbyDuplicate(nums, k):
seen = {}
for i, num in enumerate(nums):
if num in seen and i - seen[num] <= k:
return True
seen[num] = i
return FalseFrequently Asked Questions
What is the Contains Duplicate II problem?
Given an integer array and an integer k, determine if there are two distinct indices i and j such that `nums[i]` == `nums[j]` and the absolute difference between i and j is at most k. This is a sliding window problem with hash map tracking.
How do you solve Contains Duplicate II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Contains Duplicate II?
Contains Duplicate II is asked at Google, Netflix. It is a easy difficulty problem.
What are common mistakes on Contains Duplicate II?
- Using a sliding window `hash set` instead of a `hash map`. A set tells you IF the element is in the window but not WHERE. You need the index to check the distance constraint.
- Forgetting that the stored index might be outside the k-distance window. If `i - seen[num] > k`, it's a valid duplicate but too far apart. Update the stored index to the current one.
- Confusing absolute difference with exact difference. The problem says abs(i - j) <= k, which means the distance in either direction. Since we iterate left to right, we only need to check if `i - seen[num] <= k`.
- Not updating the stored index. If you keep the first occurrence, a later duplicate might falsely match against a distant first occurrence. Always update to the latest index.
- Returning true when k=0. With k=0, the only pair is (i, i) which is not two distinct indices. Return false for k=0.