220. Contains Duplicate III

Array
Sliding Window
Sorting
Bucket Sort

TIME

O(n)

SPACE

O(min(n, indexDiff))

Intuition

The textbook solution slides a window of width indexDiff and keeps its values in an ordered set, asking for the nearest neighbour of each new value. That is O(n log k). Bucketing gets the same answer in O(n).

Choose the bucket width w = valueDiff + 1. Then:

two values in the same bucket differ by at most w - 1 = valueDiff, so finding the bucket already occupied is an immediate answer, and
two values within valueDiff of each other must sit in the same bucket or in adjacent ones. They cannot be two buckets apart, because that forces a gap of more than w - 1, which is at least valueDiff.

So each new value needs exactly three lookups: its own bucket and the two neighbours. Nothing has to be ordered.

The map from bucket id to value holds at most one value per bucket, and that is not an assumption to maintain, a second value landing in an occupied bucket is precisely the condition that returns true, so the situation never persists.

The +1 in the width is what makes valueDiff = 0 fall out with no special case: w = 1 puts every integer in its own bucket, so sharing a bucket means being equal.

Approach

w = valueDiff + 1, and an empty map bucket -> value.
For each index i:
- If i > indexDiff, evict nums[i - indexDiff - 1] from its bucket, so the map holds exactly the indices [i - indexDiff, i - 1].
- b = floor(nums[i] / w). If b is in the map, return true.
- If b - 1 is in the map and nums[i] - map[b-1] <= valueDiff, return true. Likewise for b + 1 with map[b+1] - nums[i].
- Store map[b] = nums[i].
Return false.

No abs is needed in the neighbour comparisons: bucket b - 1 only holds values below b * w, which is at most nums[i], so the difference is already non-negative, and symmetrically for b + 1.

Complexity

Time: O(n), three hash lookups and one eviction per element
Space: O(min(n, indexDiff)), the map never holds more than one window

Edge Cases

valueDiff = 0 → w = 1, so a repeated bucket means an exactly equal value, which is example 1
Negative values need floor division, not truncation toward zero. -1 / 3 has to be -1; truncating gives 0 and lumps -1 with the non-negatives, which misses pairs straddling zero. Python's // floors already, Java needs Math.floorDiv
The difference nums[i] - prev reaches 2 * 10^9 and overflows a Java int, so the comparison is done in long
valueDiff = 10^9 → w = 10^9 + 1, which still fits an int (2^31 - 1 = 2147483647)
indexDiff = 1 → only adjacent indices are compared, and the eviction keeps exactly one value in the map
indexDiff >= n → nothing is ever evicted, so the whole array is one window
The window must be [i - indexDiff, i - 1], so the eviction at step i removes index i - indexDiff - 1; evicting index i - indexDiff instead would narrow the window by one and miss valid pairs
Eviction uses a defaulted pop, though the invariant guarantees the bucket is present: buckets only free up in index order, so the departing value is still the one occupying its bucket

Code

class Solution:
    def containsNearbyAlmostDuplicate(
        self, nums: list[int], indexDiff: int, valueDiff: int
    ) -> bool:
        """
        220. Contains Duplicate III
        Time: O(n)
        Space: O(min(n, indexDiff))
        """
        width = valueDiff + 1  # same bucket => difference at most valueDiff
        buckets = {}  # bucket id -> its single value, over the live window

        for i, v in enumerate(nums):
            if i > indexDiff:
                # keep the window at indices [i - indexDiff, i - 1]
                old = nums[i - indexDiff - 1]
                buckets.pop(old // width, None)

            b = v // width  # floors for negatives, which is what we need
            if b in buckets:
                return True
            # a value within valueDiff can only be in an adjacent bucket, and
            # bucket b-1 holds values below b * width <= v, so no abs needed
            if b - 1 in buckets and v - buckets[b - 1] <= valueDiff:
                return True
            if b + 1 in buckets and buckets[b + 1] - v <= valueDiff:
                return True

            buckets[b] = v

        return False

import java.util.HashMap;
import java.util.Map;

/**
 * 220. Contains Duplicate III
 * Time: O(n)
 * Space: O(min(n, indexDiff))
 */
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        // same bucket => difference at most valueDiff; width fits an int
        // because valueDiff <= 1e9
        int width = valueDiff + 1;
        // bucket id -> its single value, over the live window
        Map<Integer, Integer> buckets = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];

            if (i > indexDiff) {
                // keep the window at indices [i - indexDiff, i - 1]
                int old = nums[i - indexDiff - 1];
                buckets.remove(Math.floorDiv(old, width));
            }

            // floorDiv, not /, so negatives bucket consistently
            int b = Math.floorDiv(v, width);
            if (buckets.containsKey(b)) {
                return true;
            }
            // a value within valueDiff can only be in an adjacent bucket, and
            // bucket b-1 holds values below b * width <= v, so no abs needed.
            // The difference reaches 2e9, so compare in long.
            Integer lower = buckets.get(b - 1);
            if (lower != null && (long) v - lower <= valueDiff) {
                return true;
            }
            Integer upper = buckets.get(b + 1);
            if (upper != null && (long) upper - v <= valueDiff) {
                return true;
            }

            buckets.put(b, v);
        }

        return false;
    }
}