Solution Explanation: Sliding Window + Ordered Set

This problem asks whether there exists a pair of indices (i, j) in the input array nums that satisfy three conditions:

1. i != j
2. abs(i - j) <= indexDiff
3. 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:

1. Initialization: We use an ordered set (s) to store elements within the current sliding window. The window size is determined by indexDiff.

2. 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.

3. No nearby almost duplicate: If the loop completes without finding a pair, we return false.

Time Complexity Analysis:

• The outer loop iterates n times (where n is the length of nums).
• Inside the loop, the operations on the ordered set (insertion, removal, and finding the ceiling/bisect_left) take O(log k) time on average, where k is the maximum window size (indexDiff).
• Therefore, the overall time complexity is O(n log k). This is significantly better than the O(n²) of the brute-force approach.

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.