220. Contains Duplicate III
Asked at Netflix
Difficulty
Hard
Time
O(n)
Space
O(min(n, indexDiff))
Pattern
Array
Companies
1
Problem
You get an integer array nums and two integers indexDiff and valueDiff. Your job is to decide if there is a pair of different positions i and j that passes all three tests at once:
i != j— they are two different positions.abs(i - j) <= indexDiff— the positions are close together in the array.abs(nums[i] - nums[j]) <= valueDiff— the values at those positions are close in size.
Return true if at least one such pair exists, otherwise return false. Note that valueDiff can be 0, which means the two values must be exactly equal. The two positions must be distinct, so a single element can never pair with itself.
Two windows must overlap
Constraints
- ●
2 <= nums.length <= 10^5 - ●
-10^9 <= nums[i] <= 10^9 - ●
1 <= indexDiff <= nums.length - ●
0 <= valueDiff <= 10^9
Examples
nums = [1,2,3,1], indexDiff = 3, valueDiff = 0truenums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3falseAsked At
1 companies| 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.
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.
Buckets of width valueDiff + 1
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
O(n) timedef 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 runs in O(n) time and O(min(n, indexDiff)) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.