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] <= 109
1 <= indexDiff <= nums.length
0 <= valueDiff <= 109
This problem asks whether there exists a pair of indices (i, j) in the input array nums
that satisfy three conditions:
i != j
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
A brute-force approach would check all pairs of indices, resulting in O(n²) time complexity. However, we can optimize this using a sliding window and an ordered set (like a TreeSet
in Java or a SortedSet
in Python).
Algorithm:
Initialization: We use an ordered set (s
) to store elements within the current sliding window. The window size is determined by indexDiff
.
Iteration: We iterate through the nums
array. For each element nums[i]
:
Check for a nearby almost duplicate: We use the ordered set's bisect_left
(Python) or ceiling
(Java) method to efficiently find the smallest element in the set that is greater than or equal to nums[i] - valueDiff
. If such an element exists and is less than or equal to nums[i] + valueDiff
, then we've found a pair satisfying the conditions, and we return true
.
Add to the window: We add nums[i]
to the ordered set s
.
Remove from the window: If the window size exceeds indexDiff
, we remove nums[i - indexDiff]
(the element that's no longer within the window) from the set.
No nearby almost duplicate: If the loop completes without finding a pair, we return false
.
Time Complexity Analysis:
n
times (where n
is the length of nums
).indexDiff
).Space Complexity Analysis:
The space complexity is O(k) because the ordered set s
stores at most k
elements at any given time.
Code Examples (Python & Java):
Python:
import bisect
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):
idx = s.bisect_left(v - valueDiff) # Find the index of the smallest element >= v - valueDiff
if idx < len(s) and s[idx] <= v + valueDiff: # Check if an element within valueDiff exists
return True
s.add(v)
if i >= indexDiff:
s.remove(nums[i - indexDiff])
return False
Java:
import java.util.TreeSet;
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeSet<Long> s = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Long ceiling = s.ceiling((long) nums[i] - valueDiff); // Find the smallest element >= nums[i] - valueDiff
if (ceiling != null && ceiling <= (long) nums[i] + valueDiff) {
return true;
}
s.add((long) nums[i]);
if (i >= indexDiff) {
s.remove((long) nums[i - indexDiff]);
}
}
return false;
}
}
The other languages (C++, Go, TypeScript, C#) demonstrate similar implementations, leveraging their respective ordered set data structures. The core algorithm remains consistent across all languages.