175. Contains Duplicate III

Drop each number into a bucket of width valueDiff+1. Two numbers in the SAME bucket automatically differ by at most valueDiff. Two numbers in ADJACENT buckets might, so check those explicitly. Keep only the last indexDiff buckets alive (a sliding window) so index distance is bounded.

Buckets guarantee the value condition

Use buckets of width w = valueDiff + 1. Any two numbers that land in the same bucket differ by at most valueDiff — an instant hit. Numbers in neighbouring buckets might be within valueDiff, so those are the only extra pairs worth checking.

The bucket id for value x is floor(x / w) (use floor division so negatives bucket correctly).

Sliding window on indices

To enforce abs(i - j) <= indexDiff, keep at most indexDiff recent numbers: when the window grows past that, evict the number that left the window (nums[i - indexDiff]) from its bucket.

w = valueDiff + 1; buckets = {}
for i, x in enumerate(nums):
    b = x // w
    if b in buckets: return True                       # same bucket
    if b-1 in buckets and x - buckets[b-1] <= valueDiff: return True
    if b+1 in buckets and buckets[b+1] - x <= valueDiff: return True
    buckets[b] = x
    if i >= indexDiff: remove bucket of nums[i-indexDiff]
return False

Each bucket holds at most one number because a second one in the same bucket would return immediately.

Worked example

nums = [1, 2, 3, 1], indexDiff = 3, valueDiff = 0 → w = 1, bucket id = value.

• i=0: 1 → bucket 1.
• i=1: 2 → bucket 2.
• i=2: 3 → bucket 3.
• i=3: 1 → bucket 1 already present → return true (indices 0 and 3, |0-3|=3 <= 3).

Complexity

• Time: O(n) — each index does O(1) bucket work.
• Space: O(min(n, indexDiff)).

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        if (valueDiff < 0) return false;
        long w = (long) valueDiff + 1;
        Map<Long, Long> buckets = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            long b = Math.floorDiv(x, w);
            if (buckets.containsKey(b)) return true;
            if (buckets.containsKey(b - 1) && Math.abs(x - buckets.get(b - 1)) <= valueDiff) return true;
            if (buckets.containsKey(b + 1) && Math.abs(x - buckets.get(b + 1)) <= valueDiff) return true;
            buckets.put(b, x);
            if (i >= indexDiff) {
                buckets.remove(Math.floorDiv((long) nums[i - indexDiff], w));
            }
        }
        return false;
    }
}