Contains Duplicate III

hard array sliding window bucket sort

Problem

Return true if there exist indices i ≠ j with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff. Use buckets of width valueDiff + 1; values within the same bucket are automatically within valueDiff of each other.

Inputnums = [1, 5, 9, 1, 5, 9], indexDiff = 2, valueDiff = 3

Outputfalse

Within any window of size 3 the closest pair (e.g. 1 and 5) differs by 4 — never ≤ 3.

nums (comma-separated)

indexDiff

valueDiff

def containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff):
    if valueDiff < 0:
        return False
    w = valueDiff + 1
    buckets = {}
    for i, x in enumerate(nums):
        b = x // w
        if b in buckets:
            return True
        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:
            del buckets[nums[i - indexDiff] // w]
    return False

function containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff) {
  if (valueDiff < 0) return false;
  const w = valueDiff + 1;
  const buckets = new Map();
  const bucketOf = (x) => Math.floor(x / w);
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i], b = bucketOf(x);
    if (buckets.has(b)) return true;
    if (buckets.has(b - 1) && x - buckets.get(b - 1) <= valueDiff) return true;
    if (buckets.has(b + 1) && buckets.get(b + 1) - x <= valueDiff) return true;
    buckets.set(b, x);
    if (i >= indexDiff) buckets.delete(bucketOf(nums[i - indexDiff]));
  }
  return false;
}

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) && x - buckets.get(b - 1) <= valueDiff) return true;
            if (buckets.containsKey(b + 1) && buckets.get(b + 1) - x <= valueDiff) return true;
            buckets.put(b, x);
            if (i >= indexDiff) buckets.remove(Math.floorDiv((long) nums[i - indexDiff], w));
        }
        return false;
    }
}

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        if (valueDiff < 0) return false;
        long w = (long)valueDiff + 1;
        unordered_map<long, long> buckets;
        auto floorDiv = [&](long x) { return x >= 0 ? x / w : -((-x + w - 1) / w); };
        for (int i = 0; i < (int)nums.size(); i++) {
            long x = nums[i], b = floorDiv(x);
            if (buckets.count(b)) return true;
            if (buckets.count(b - 1) && x - buckets[b - 1] <= valueDiff) return true;
            if (buckets.count(b + 1) && buckets[b + 1] - x <= valueDiff) return true;
            buckets[b] = x;
            if (i >= indexDiff) buckets.erase(floorDiv(nums[i - indexDiff]));
        }
        return false;
    }
};

Explanation

This is the tricky cousin of the duplicate problem: we need two values that are close in index (within indexDiff) and close in value (within valueDiff). The clever idea is bucketing numbers so that "close in value" becomes "same or neighbouring bucket".

We make each bucket valueDiff + 1 wide and compute a number's bucket as x // w. Why +1? It guarantees that any two numbers landing in the same bucket differ by at most valueDiff — an instant hit.

For each new number we check three buckets: its own (a direct collision means a pair), and the two neighbours b - 1 and b + 1, where we still verify the actual difference is within valueDiff. The map stores one representative value per bucket.

To enforce the index window, we slide along and once i >= indexDiff we delete the bucket of the element that just fell out of range (nums[i - indexDiff]). So the map only ever holds the current window.

Example: nums = [1, 5, 9, 1], indexDiff = 3, valueDiff = 0. Width is 1, every value sits in its own bucket. The two 1s share a bucket and are within 3 indices, so the answer is true.

Time: O(n) average Space: O(min(n, indexDiff))