200. Contains Duplicate III
The final variation loosens both requirements. You receive an integer array nums and two integers indexDiff and valueDiff. Return true if there exists a pair of distinct positions i != j that is close in both senses at once:
- close in position:
|i - j| <= indexDiff, and - close in value:
|nums[i] - nums[j]| <= valueDiff.
Otherwise return false. The values no longer need to be equal — they just need to land within valueDiff of each other while sitting within indexDiff positions of each other. The challenge is answering "is there any value near mine?" inside a sliding window without comparing against every window element.
Example 1:
Input: nums = [1, 2, 3, 1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: Positions 0 and 3 hold the same value 1: the index gap is 3 <= indexDiff and the value gap is 0 <= valueDiff.
Example 2:
Input: nums = [1, 5, 9, 1, 5, 9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: Inside any window of width 2 the values differ by at least 4, and the equal values sit 3 positions apart — no pair satisfies both limits.
Constraints:
- 2 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
- 1 ≤ indexDiff ≤ 10⁴
- 0 ≤ valueDiff ≤ 10⁹
Hints:
Keep a window of the last indexDiff elements. The question per element becomes: does the window contain any value in [x - valueDiff, x + valueDiff]?
An ordered structure answers that with one lookup: find the smallest window value >= x - valueDiff and test whether it is <= x + valueDiff. That's a multiset / TreeSet ceiling query, O(log k) per element.
For O(n): drop each value into a bucket of width valueDiff + 1 (bucket id = floor(x / width)). Two values in the same bucket are automatically close enough, and only the two neighboring buckets can hold another candidate.
Mind the details: use floor division for negative values, evict the element that leaves the window, and beware overflow — value gaps can reach 2 × 10^9.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3, 1], indexDiff = 3, valueDiff = 0
Expected output: true