Brute Force Solution

The most straightforward approach is to iterate through all possible pairs of indices (i, j) in the array and check if they satisfy the given conditions. This involves nested loops, where the outer loop iterates from i = 0 to n - 1, and the inner loop iterates from j = 0 to n - 1. Inside the inner loop, we check if i != j, abs(i - j) <= indexDiff, and abs(nums[i] - nums[j]) <= valueDiff. If all three conditions are met, we return true. If we finish iterating through all possible pairs without finding a valid pair, we return false.

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && Math.abs(i - j) <= indexDiff && Math.abs((long)nums[i] - (long)nums[j]) <= valueDiff) {
                    return true;
                }
            }
        }
        return false;
    }
}

Time Complexity

The time complexity of the brute force solution is O(n^2), where n is the length of the input array nums, because of the nested loops.

Space Complexity

The space complexity of the brute force solution is O(1), as it uses only a constant amount of extra space.

Optimal Solution (Using Sliding Window and TreeSet)

To improve the time complexity, we can use a sliding window and a TreeSet. The TreeSet will store the numbers within the current window of size indexDiff. For each number nums[i], we can use the TreeSet to find the smallest number greater than or equal to nums[i] - valueDiff and the largest number less than or equal to nums[i] + valueDiff. If either of these numbers exist within the TreeSet, it means we have found a pair that satisfies the conditions.

1. Initialize a TreeSet to store numbers within the sliding window.
2. Iterate through the nums array from i = 0 to n - 1.
3. For each nums[i], use treeSet.ceiling(nums[i] - valueDiff) to find the smallest number in the TreeSet that is greater than or equal to nums[i] - valueDiff.
4. If such a number exists and is less than or equal to nums[i] + valueDiff, return true.
5. Add nums[i] to the TreeSet.
6. If i >= indexDiff, remove nums[i - indexDiff] from the TreeSet to maintain the sliding window size.
7. If the loop finishes without finding a valid pair, return false.

import java.util.TreeSet;

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long floor = set.floor((long)nums[i] + valueDiff);
            Long ceiling = set.ceiling((long)nums[i] - valueDiff);
            if ((floor != null && floor >= (long)nums[i]) || (ceiling != null && ceiling <= (long)nums[i])) {
                return true;
            }
            set.add((long)nums[i]);
            if (i >= indexDiff) {
                set.remove((long)nums[i - indexDiff]);
            }
        }
        return false;
    }
}

Time Complexity

The time complexity of the optimal solution is O(n log k), where n is the length of the input array nums and k is the window size (indexDiff). The TreeSet operations (ceiling, floor, add, and remove) take O(log k) time each.

Space Complexity

The space complexity of the optimal solution is O(k), as the TreeSet stores at most indexDiff elements.