Sponsored
Sponsored
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.
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.
1import java.util.TreeSet;
2
3public class Solution {
4 public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
5 if (indexDiff <= 0 || valueDiff < 0) return false;
6 TreeSet<Long> set = new TreeSet<>();
7 for (int i = 0; i < nums.length; i++) {
8 long num = (long) nums[i];
9 Long floor = set.floor(num + valueDiff);
10 Long ceil = set.ceiling(num - valueDiff);
11 if ((floor != null && floor >= num) || (ceil != null && ceil <= num)) {
12 return true;
13 }
14 set.add(num);
15 if (i >= indexDiff)
16 set.remove((long) nums[i - indexDiff]);
17 }
18 return false;
19 }
20}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.
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.
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.
1import java.util.HashMap;
2
3We 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.