LeetCode 220: Contains Duplicate III

Explanation

To solve this problem, we can iterate through each element in the array and maintain a sliding window of size indexDiff. For each element, we check if there exists any previous element within the window such that the absolute difference between the current element and the previous element is less than or equal to valueDiff.

We can use a TreeSet (Red-Black Tree) in Java or a multiset in C++ to efficiently retrieve the previous element within the window. By maintaining this window, we can efficiently check if the conditions are satisfied.

• Time complexity: O(n * log(min(n, k))), where n is the length of the input array and k is the size of the window.
• Space complexity: O(min(n, k))

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 >= nums[i]) || (ceiling != null && ceiling <= nums[i])) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= indexDiff) {
                set.remove((long) nums[i - indexDiff]);
            }
        }
        return false;
    }
}