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, andReturn 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) <= 0
Example 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 <= 109Problem Overview: Given an integer array, determine whether two different indices i and j exist such that |i - j| ≤ k and |nums[i] - nums[j]| ≤ t. The challenge is enforcing both the index distance and value distance constraints efficiently without checking every pair.
Approach 1: Sliding Window with TreeSet (O(n log k) time, O(k) space)
This approach maintains a sliding window of size k containing the last k elements while iterating through the array. An ordered structure like TreeSet (Java) or a balanced sorted container is used so you can quickly find the closest numbers to the current value. For each element nums[i], search the set for the smallest number greater than or equal to nums[i] - t. If that candidate is ≤ nums[i] + t, the condition is satisfied. Insert the current value into the set and remove the element that slides out when the window exceeds size k. Ordered lookup and insertion take O(log k), giving total O(n log k) time with O(k) space. This technique combines sliding window logic with an ordered set to enforce both constraints efficiently.
Approach 2: Bucketing Technique (O(n) time, O(n) space)
The bucket method achieves linear time by grouping numbers into ranges of width t + 1. If two numbers differ by at most t, they must fall into either the same bucket or adjacent buckets. For each element, compute its bucket ID using integer division. First check whether the current bucket already contains a number. Then check the neighboring buckets because their values could still be within distance t. Store the current number in its bucket and maintain the k-sized window by removing the bucket corresponding to nums[i - k]. Each lookup, insertion, and deletion is constant time using a hash map, producing O(n) time and O(n) space. This approach relies on value partitioning rather than ordering and is closely related to bucket sort ideas applied to an array traversal.
Recommended for interviews: The sliding window with an ordered set is often the expected solution because it demonstrates understanding of balanced search trees and range queries. The bucket approach is more optimal at O(n) but requires a key insight about bucket width and careful handling of negative numbers and overflow. Showing the TreeSet solution first proves you understand the constraint interaction, while implementing the bucket technique signals stronger algorithmic intuition.
This approach uses a sliding window technique to maintain a set of the current window elements. TreeSet (or equivalent in other languages) is used to efficiently handle range-based queries within the window. By maintaining a set of elements within indexDiff, we can quickly check if there is a number within valueDiff of the current number.
The implementation uses a TreeSet to maintain elements within a sliding window of size indexDiff. For each element, we check for the existence of any number in the set that differs by at most valueDiff from the current number. The floor and ceiling methods efficiently find potential candidates within the set. After processing each element, we update the set by adding the current number and removing the one that falls out of the window.
Time complexity: O(n log k) where n is the length of the array and k is indexDiff, due to logarithmic time complexity of TreeSet operations.
Space complexity: O(k) since we store at most indexDiff elements in the set.
This approach involves bucketing the numbers using their division by (valueDiff + 1). Each bucket can contain numbers that satisfy the valueDiff condition. We keep track of active buckets for indices falling within the indexDiff range.
We bucket each number by dividing it by (valueDiff + 1). This ensures that two numbers within a difference of valueDiff end up in the same or neighboring buckets. As we traverse the array, we check the current, previous, and next buckets for possible candidates.
Time complexity: O(n), where n is the number of elements, as each operation (insert, check, remove) is constant time on average.
Space complexity: O(k), due to the hash map's storage for at most k buckets.
We maintain a sliding window of size k, and the elements in the window are kept in order.
We traverse the array nums. For each element nums[i], we look for the first element in the ordered set that is greater than or equal to nums[i] - t. If the element exists, and this element is less than or equal to nums[i] + t, it means we have found a pair of elements that meet the conditions, and we return true. Otherwise, we insert nums[i] into the ordered set, and if the size of the ordered set exceeds k, we need to remove the earliest added element from the ordered set.
The time complexity is O(n times log k), where n is the length of the array nums. For each element, we need O(log k) time to find the element in the ordered set, and there are n elements in total, so the total time complexity is O(n times log k).
| Approach | Complexity |
|---|---|
| Sliding Window with TreeSet | Time complexity: |
| Bucketing Technique | Time complexity: |
| Sliding Window + Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with TreeSet | O(n log k) | O(k) | General interview solution when ordered range queries are easy to implement |
| Bucketing Technique | O(n) | O(n) | Best performance when constant-time hashing is available and bucket logic is implemented carefully |
Contains Duplicate iii | LeetCode 220 | C++, Python • Knowledge Center • 22,170 views views
Watch 9 more video solutions →Practice Contains Duplicate III with our built-in code editor and test cases.
Practice on FleetCode