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.
1from sortedcontainers import SortedList
2
3def contains_nearby_almost_duplicate(nums, indexDiff, valueDiff):
4 if indexDiff <= 0 or valueDiff < 0:
5 return False
6
7 sorted_list = SortedList()
8 for i in range(len(nums)):
9 if i > indexDiff:
10 sorted_list.remove(nums[i - indexDiff - 1])
11 pos1 = SortedList.bisect_left(sorted_list, nums[i] - valueDiff)
12 pos2 = SortedList.bisect_right(sorted_list, nums[i] + valueDiff)
13 if pos1 != pos2:
14 return True
15 sorted_list.add(nums[i])
16 return FalseThis solution utilizes SortedList from sortedcontainers to mimic the functionality of a TreeSet, allowing range-based queries within the sliding window. The list is maintained such that it contains elements within indexDiff.
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.