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) <= 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
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)
if j < len(s) and s[j] <= v + valueDiff:
return True
s.add(v)
if i >= indexDiff:
s.remove(nums[i - indexDiff])
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;
}
};
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
n := len(nums)
left, right := 0, 0
rbt := redblacktree.NewWithIntComparator()
for right < n {
cur := nums[right]
right++
if p, ok := rbt.Floor(cur); ok && cur-p.Key.(int) <= t {
return true
}
if p, ok := rbt.Ceiling(cur); ok && p.Key.(int)-cur <= t {
return true
}
rbt.Put(cur, struct{}{})
if right-left > k {
rbt.Remove(nums[left])
left++
}
}
return false
}
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;
}
}