Contains Duplicate III
HardPrompt
You are given an integer array nums and two integers indexDiff and valueDiff.
Find a pair of indices (i, j) such that:
i != j,abs(i - j) <= indexDiff.abs(nums[i] - nums[j]) <= valueDiff, and
Return true if such pair exists or false otherwise.
Example 1:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0Example 2:
Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.
Constraints:
2 <= nums.length <= 105-109 <= nums[i] <= 1091 <= indexDiff <= nums.length0 <= valueDiff <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
Check every possible pair of indices (i,j) in the array and verify if they satisfy all three conditions.
Algorithm
- Iterate through each index i from 0 to n-1
- For each i, iterate through j from i+1 to n-1
- Check if |i-j| ≤ indexDiff
- Check if |nums[i] - nums[j]| ≤ valueDiff
- If both conditions are met, return true
- If no such pair is found, return false
Walkthrough
For each index i in the array, we check all possible indices j that come after i. For each pair, we verify:
- If i and j are different (always true in this case)
- If the absolute difference between indices (|i-j|) is less than or equal to indexDiff
- If the absolute difference between values (|nums[i] - nums[j]|) is less than or equal to valueDiff
Here's the implementation:
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (Math.abs(i - j) <= indexDiff && Math.abs((long)nums[i] - nums[j]) <= valueDiff) { return true; } } } return false;}Note: We use long for the value difference calculation to handle potential integer overflow cases.
Complexity
Time
O(n²) where n is the length of the array as we need to check every possible pair
Space
O(1) as we only use a constant amount of extra space
Trade-offs
Pros
Simple to implement
No extra space required
Works for all input cases
Cons
Very slow for large arrays
Inefficient as it checks all possible pairs
Not suitable for large inputs due to quadratic time complexity
Use a TreeSet to maintain a sorted window of elements and efficiently find elements within the value difference range.
Algorithm
- Create a TreeSet to store numbers in the current window
- For each number in the array:
- Check if there exists a number in set within range [curr-valueDiff, curr+valueDiff]
- Add current number to set
- Remove number that's outside the window (i-indexDiff)
- Return true if a valid pair is found, false otherwise
Walkthrough
We maintain a sliding window of size indexDiff+1 using a TreeSet. For each number, we try to find an existing number in our set that satisfies the valueDiff condition using TreeSet's ceiling and floor methods.
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { if (nums == null || nums.length < 2 || indexDiff < 1 || valueDiff < 0) return false; TreeSet<Long> set = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { long curr = nums[i]; // Find the smallest number greater than or equal to curr-valueDiff Long floor = set.floor(curr + valueDiff); Long ceiling = set.ceiling(curr - valueDiff); if ((floor != null && floor >= curr) || (ceiling != null && ceiling <= curr)) { return true; } set.add(curr); // Remove the element outside the window if (i >= indexDiff) { set.remove((long)nums[i - indexDiff]); } } return false;}Complexity
Time
O(n log k) where n is the length of array and k is the size of the sliding window (indexDiff)
Space
O(k) where k is the size of the sliding window (indexDiff)
Trade-offs
Pros
More efficient than brute force approach
Handles large inputs better
Maintains only necessary elements in the window
Cons
Requires extra space for TreeSet
TreeSet operations are more expensive than simple array operations
More complex implementation
Use bucket sort concept to group numbers into buckets based on their values and check for nearby duplicates.
Algorithm
- Create buckets of size valueDiff+1
- For each number:
- Calculate its bucket ID
- Check if same bucket already has a number
- Check adjacent buckets for numbers within valueDiff range
- Add current number to its bucket
- Remove number outside the window
- Return true if a valid pair is found, false otherwise
Walkthrough
We divide the numbers into buckets where each bucket has size valueDiff+1. Numbers that could satisfy the valueDiff condition must fall into the same bucket or adjacent buckets.
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { if (nums == null || nums.length < 2 || indexDiff < 1 || valueDiff < 0) return false; Map<Long, Long> buckets = new HashMap<>(); long w = (long)valueDiff + 1; for (int i = 0; i < nums.length; i++) { long remappedNum = (long)nums[i] - Integer.MIN_VALUE; long bucketId = remappedNum / w; // Check if the current bucket has a number if (buckets.containsKey(bucketId)) return true; // Check adjacent buckets if (buckets.containsKey(bucketId - 1) && Math.abs(buckets.get(bucketId - 1) - remappedNum) < w) return true; if (buckets.containsKey(bucketId + 1) && Math.abs(buckets.get(bucketId + 1) - remappedNum) < w) return true; // Add current number to bucket buckets.put(bucketId, remappedNum); // Remove number outside the window if (i >= indexDiff) { long lastNum = (long)nums[i - indexDiff] - Integer.MIN_VALUE; long lastBucketId = lastNum / w; buckets.remove(lastBucketId); } } return false;}Complexity
Time
O(n) where n is the length of the array as we only need to traverse the array once
Space
O(min(n, k)) where k is indexDiff as we only store elements within the window
Trade-offs
Pros
Most efficient approach for this problem
O(1) lookup time for potential matches
Handles large inputs efficiently
Cons
Requires careful handling of integer overflow
More complex implementation
Uses extra space for storing buckets
Solutions
Solution
public class Solution { public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (k <= 0 || t < 0) return false; var index = new SortedList < int, object > (); for (int i = 0; i < nums.Length; ++i) { if (index.ContainsKey(nums[i])) { return true; } index.Add(nums[i], null); var j = index.IndexOfKey(nums[i]); if (j > 0 && (long) nums[i] - index.Keys[j - 1] <= t) { return true; } if (j < index.Count - 1 && (long) index.Keys[j + 1] - nums[i] <= t) { return true; } if (index.Count > k) { index.Remove(nums[i - k]); } } return false; }}class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { TreeSet<Long> ts = new TreeSet<>(); for (int i = 0; i < nums.length; ++i) { Long x = ts.ceiling((long)nums[i] - (long)valueDiff); if (x != null && x <= (long)nums[i] + (long)valueDiff) { return true; } ts.add((long)nums[i]); if (i >= indexDiff) { ts.remove((long)nums[i - indexDiff]); } } return false; }}class Solution {public: bool containsNearbyAlmostDuplicate(vector<int> &nums, int indexDiff, int valueDiff) { set<long> s; for (int i = 0; i < nums.size(); ++i) { auto it = s.lower_bound((long)nums[i] - valueDiff); if (it != s.end() && *it <= (long)nums[i] + valueDiff) return true; s.insert((long)nums[i]); if (i >= indexDiff) s.erase((long)nums[i - indexDiff]); } return false; }};''' Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions. >>> from sortedcontainers import SortedList >>> sl = SortedList(['e', 'a', 'c', 'd', 'b']) >>> sl SortedList(['a', 'b', 'c', 'd', 'e']) >>> sl *= 10_000_000 >>> sl.count('c') 10000000 >>> sl[-3:] ['e', 'e', 'e'] >>> from sortedcontainers import SortedDict >>> sd = SortedDict({'c': 3, 'a': 1, 'b': 2}) >>> sd SortedDict({'a': 1, 'b': 2, 'c': 3}) >>> sd.popitem(index=-1) ('c', 3) >>> from sortedcontainers import SortedSet >>> ss = SortedSet('abracadabra') >>> ss SortedSet(['a', 'b', 'c', 'd', 'r']) >>> ss.bisect_left('c') 2 ref: https://pypi.org/project/sortedcontainers/ ''' from sortedcontainers import SortedSet class Solution : def containsNearbyAlmostDuplicate ( self , nums : List [ int ], indexDiff : int , valueDiff : int ) -> bool : s = SortedSet () for i , v in enumerate ( nums ): j = s . bisect_left ( v - valueDiff ) # then true: s[j] <= v - valueDiff if j < len ( s ) and s [ j ] <= v + valueDiff : return True s . add ( v ) if i >= indexDiff : s . remove ( nums [ i - indexDiff ]) return False ############ ''' bisect: maintaining a list in sorted order without having to sort the list after each insertion. https://docs.python.org/3/library/bisect.html bisect.bisect_left() Locate the insertion point for x in a to maintain sorted order. bisect.bisect_right() or bisect.bisect() Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a. bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None) Insert x in a in sorted order. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step. bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None) bisect.insort(a, x, lo=0, hi=len(a), *, key=None) Similar to insort_left(), but inserting x in a after any existing entries of x. >>> import bisect >>> bisect.bisect_left([1,2,3], 2) 1 >>> bisect.bisect_right([1,2,3], 2) 2 >>> a = [1, 1, 1, 2, 3] >>> bisect.insort_left(a, 1.0) >>> a [1.0, 1, 1, 1, 2, 3] >>> a = [1, 1, 1, 2, 3] >>> bisect.insort_right(a, 1.0) >>> a [1, 1, 1, 1.0, 2, 3] >>> a = [1, 1, 1, 2, 3] >>> bisect.insort(a, 1.0) >>> a [1, 1, 1, 1.0, 2, 3] ''' import bisect class Solution ( object ): def containsNearbyAlmostDuplicate ( self , nums , k , t ): """ :type nums: List[int] :type k: int :type t: int :rtype: bool """ if k == 0 : return False bst = [] if k < 0 or t < 0 : return False for i , num in enumerate ( nums ): idx = bisect . bisect_left ( bst , num ) if idx < len ( bst ) and abs ( bst [ idx ] - num ) <= t : return True if idx > 0 and abs ( bst [ idx - 1 ] - num ) <= t : # idx-1 is because, [3,4,5] and 3.5 insertion-index is 1, but here should check index=0 (i.e. 3), so idx-1 return True if len ( bst ) >= k : del bst [ bisect . bisect_left ( bst , nums [ i - k ])] bisect . insort ( bst , num ) return FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.