Contains Duplicate III
Asked at Netflix
Problem
Given an integer array nums and two integers indexDiff and valueDiff, return true if there exist two distinct indices i and j such that |i-j| <= indexDiff and |nums[i]-nums[j]| <= valueDiff. This extends Contains Duplicate II by adding a value proximity constraint.
Asked At
| Company | Difficulty | |
|---|---|---|
| Netflix | Hard | View all Netflix questions → |
How to Think About It
Brute force: check all pairs (i,j) with |i-j| <= indexDiff and |nums[i]-nums[j]| <= valueDiff. Time O(n * indexDiff) which can be O(n^2) in the worst case.
Key insight: bucket sort (address book). Numbers within valueDiff of each other fall into the same or adjacent buckets. Bucket width = valueDiff + 1. For each number, check the same bucket and neighboring buckets.
Why valueDiff + 1 as bucket width: if two numbers differ by at most valueDiff, they must be in the same bucket (when bucket width = valueDiff+1) or adjacent buckets. This guarantees we only check 3 buckets per number.
Sliding window: maintain at most indexDiff elements in the bucket map. When i > indexDiff, remove nums[i - indexDiff] from its bucket. This ensures |i-j| <= indexDiff.
Visual walkthrough for nums=[1,2,3,1], indexDiff=3, valueDiff=0: bucket width=1. num=1 -> bucket 1. num=2 -> bucket 2. num=3 -> bucket 3. num=1 -> bucket 1: same bucket exists (index 0, distance 3 <= 3). Return true.
Edge cases: valueDiff=0 means exact duplicate within indexDiff. indexDiff=0 means no valid pairs. Empty array returns false.
Optimal Approach
Step 1: Set bucket width = valueDiff + 1.
Step 2: For each index i, compute bucket = nums[i] // width.
Step 3: Check if the same bucket already has a number (guaranteed within valueDiff).
Step 4: Check if the left neighbor bucket has a number with nums[i] - left <= valueDiff.
Step 5: Check if the right neighbor bucket has a number with right - nums[i] <= valueDiff.
Step 6: If any match, return true. Otherwise, add nums[i] to its bucket.
Step 7: When i >= indexDiff, remove nums[i - indexDiff] from its bucket to maintain the window.
Step 8: If no match found after the loop, return false.
Walkthrough for nums=[1,5,9,1,5,9], indexDiff=2, valueDiff=3:
- width=4. i=0, num=1, bucket=0: empty. Add.
- i=1, num=5, bucket=1: check buckets 0,1,2. Bucket 0 has 1. 5-1=4 > 3. No match. Add.
- i=2, num=9, bucket=2: check 1,2,3. Bucket 1 has 5. 9-5=4 > 3. No match. Add.
- i=3, num=1, bucket=0: bucket 0 has old 1 (index 0, dist=3 > 2). Remove index 0 first. Bucket 0 now empty. Add index 3.
- No match. Return false.
Time: O(n) - each element is inserted and removed from buckets at most once. Space: O(min(n, indexDiff)) for the bucket map.
What Trips People Up in Real Interviews
Using bucket width = valueDiff instead of valueDiff + 1. With width = valueDiff, two numbers that differ by exactly valueDiff might land in different non-adjacent buckets.
Forgetting to remove old elements from the bucket map. Without removal, the window is unbounded and you lose the |i-j| <= indexDiff constraint.
Using sorted containers instead of bucket sort. A TreeMap works but bucket sort is simpler and O(n) average. Both are acceptable.
Checking more than 3 buckets (same, left, right). With bucket width = valueDiff+1, numbers in the same or adjacent bucket are the only candidates. No need to check further.
Off-by-one in the sliding window removal. Remove nums[i - indexDiff] when i >= indexDiff, not i > indexDiff.
Solution Code
def containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):
if indexDiff <= 0 or valueDiff < 0:
return False
buckets = {}
width = valueDiff + 1
for i, x in enumerate(nums):
b = x // width
if b in buckets:
return True
if b - 1 in buckets and x - buckets[b - 1] <= valueDiff:
return True
if b + 1 in buckets and buckets[b + 1] - x <= valueDiff:
return True
buckets[b] = x
if i >= indexDiff:
del buckets[nums[i - indexDiff] // width]
return FalseFrequently Asked Questions
What is the Contains Duplicate III problem?
Given an integer array nums and two integers indexDiff and valueDiff, return true if there exist two distinct indices i and j such that |i-j| <= indexDiff and |nums[i]-nums[j]| <= valueDiff. This extends Contains Duplicate II by adding a value proximity constraint.
How do you solve Contains Duplicate III?
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 III?
Contains Duplicate III is asked at Netflix. It is a hard difficulty problem.
What are common mistakes on Contains Duplicate III?
- Using bucket width = valueDiff instead of valueDiff + 1. With width = valueDiff, two numbers that differ by exactly valueDiff might land in different non-adjacent buckets.
- Forgetting to remove old elements from the bucket map. Without removal, the window is unbounded and you lose the |i-j| <= indexDiff constraint.
- Using sorted containers instead of bucket sort. A TreeMap works but bucket sort is simpler and `O(n)` average. Both are acceptable.
- Checking more than 3 buckets (same, left, right). With bucket width = valueDiff+1, numbers in the same or adjacent bucket are the only candidates. No need to check further.
- Off-by-one in the sliding window removal. Remove nums[i - indexDiff] when i >= indexDiff, not i > indexDiff.