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: You are given an integer array nums and two integers k and t. The task is to determine whether there exist two different indices i and j such that |i - j| ≤ k and |nums[i] - nums[j]| ≤ t. The challenge is efficiently checking both the index distance constraint and the value difference constraint at the same time.
Approach 1: Sliding Window with TreeSet (O(n log k) time, O(k) space)
This approach maintains a sliding window of size k using an ordered data structure such as a TreeSet (or SortedSet). As you iterate through the array, the window represents elements whose indices differ from the current index by at most k. For each number, perform a range query in the ordered set to check whether a value exists within [nums[i] - t, nums[i] + t]. Balanced tree operations like insertion, deletion, and lookup take O(log k) time. This approach works well when you want a clear implementation using an ordered set combined with a sliding window.
Approach 2: Bucketing Technique (O(n) time, O(n) space)
The bucket strategy groups numbers into ranges of size t + 1. Two numbers that differ by at most t must either fall into the same bucket or adjacent buckets. While iterating, compute the bucket ID for each element and check the current bucket plus its neighbors. If any stored value satisfies the difference constraint, the answer is true. Maintain the index constraint by removing elements that fall outside the last k positions. Hash map lookups make bucket checks constant time, giving an overall O(n) solution. This technique is a classic use of bucket-based partitioning for range queries.
Recommended for interviews: The bucketing technique is typically considered the optimal solution because it achieves O(n) time while enforcing both constraints efficiently. However, many candidates start with the sliding window + ordered set method since it is easier to reason about and still performs well with O(n log k) complexity. Showing the TreeSet idea demonstrates understanding of ordered data structures, while deriving the bucket optimization signals stronger algorithmic insight.
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.
Python
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.
Python
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.
| Approach | Complexity |
|---|---|
| Sliding Window with TreeSet | Time complexity: |
| Bucketing Technique | Time complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with TreeSet | O(n log k) | O(k) | General approach when using ordered sets or balanced trees for range queries |
| Bucketing Technique | O(n) | O(n) | Best performance when constant-time bucket hashing can be applied |
Contains Duplicate - Leetcode 217 - Python • NeetCode • 770,501 views views
Watch 9 more video solutions →Practice Contains Duplicate III with our built-in code editor and test cases.
Practice on FleetCode