Contains Duplicate III

Intuitionturning two distance conditions into a local bucket check

When you process nums[i], index j can only come from the previous indexDiff positions. That turns the first condition into a sliding-window rule: keep exactly the recent values that are still allowed partners for the current value, and remove each value when it becomes too old. The remaining challenge is checking whether one of those values is within valueDiff of nums[i].

Choose bucket width w = valueDiff + 1. Any two values in the same bucket differ by at most valueDiff, so finding the current value's bucket occupied is immediately enough. A valid value in a neighboring bucket is also possible, but only when it lies close enough to the bucket boundary. No bucket farther away can contain a valid partner.

The width is one larger than valueDiff so that a bucket never contains two values whose difference could exceed the allowed difference. For example, with valueDiff equal to 3, every bucket spans four integer values. The bucket map stores one value per bucket; if a second value reaches the same bucket, the answer is already true, so there is no need to preserve both.

Approach

1. 1Set the bucket width to valueDiff + 1 and use long long arithmetic, because the width must separate same-bucket values correctly and subtracting two extreme int values can overflow int.
2. 2Scan nums from left to right, because every earlier value is either still inside the index window or is already too old to matter.
3. 3Map nums[i] to its bucket using floor-style division, including a special rule for negative values, because ordinary C++ division truncates toward zero and would put negative values into inconsistent buckets.
4. 4Return true if the current bucket is occupied, because two distinct values in one bucket differ by at most valueDiff.
5. 5Check the immediately lower and higher buckets and verify the actual difference, because a neighboring bucket may be close to the current bucket without containing a close enough value.
6. 6Insert the current value into its bucket only after all checks, because the pair must use distinct indices and the current value must not match itself.
7. 7When i is at least indexDiff, erase nums[i - indexDiff], because that index is exactly outside the allowed window for the next current position; keeping it would accept an invalid index pair.

Complexityexpected bounds for the hash-map bucket solution

Annotated solutionC++ · bucket map · one pass over the array

#include <cstdlib>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        long long width = static_cast<long long>(valueDiff) + 1;
        unordered_map<long long, long long> buckets;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            long long value = nums[i];
            long long id = getBucketId(value, width);

            if (buckets.count(id)) {
                return true;
            }

            if (buckets.count(id - 1) &&
                llabs(value - buckets[id - 1]) < width) {
                return true;
            }

            if (buckets.count(id + 1) &&
                llabs(value - buckets[id + 1]) < width) {
                return true;
            }

            buckets[id] = value;

            if (i >= indexDiff) {
                long long oldValue = nums[i - indexDiff];
                long long oldId = getBucketId(oldValue, width);
                buckets.erase(oldId);
            }
        }

        return false;
    }

private:
    long long getBucketId(long long value, long long width) {
        if (value >= 0) {
            return value / width;
        }
        return (value + 1) / width - 1;
    }
};

The negative-value formula implements floor division rather than C++'s truncation toward zero. With width 4, values 0 through 3 belong to bucket 0, while -1 through -4 belong to bucket -1. That makes every bucket a genuine consecutive interval of width four, so the same-bucket and neighboring-bucket arguments remain valid across zero.

The erase operation is safe even though the map stores only one value per bucket. If a newer value had already occupied the same bucket as the value being removed, the algorithm would have returned true when that newer value was processed. Therefore, on every path that continues, each active bucket has at most one value, and erasing the old value cannot accidentally remove a different active value.

The ordered-set alternativea different arrangement that avoids bucket arithmetic

A multiset can keep the active window sorted and find the first value at least current - valueDiff. If that value is at most current + valueDiff, it forms a valid pair. This version is not an optimisation: it costs O(n log d) time instead of expected O(n), but it is often easier to reason about and handles negative values without a custom bucket mapping. The multiset is necessary because equal values may appear at different indices.

#include <set>
#include <vector>

using namespace std;

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        multiset<long long> window;
        long long limit = valueDiff;

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            if (i > indexDiff) {
                auto old = window.find(nums[i - indexDiff - 1]);
                window.erase(old);
            }

            long long value = nums[i];
            auto candidate = window.lower_bound(value - limit);
            if (candidate != window.end() && *candidate <= value + limit) {
                return true;
            }

            window.insert(value);
        }

        return false;
    }
};

Common mistakesthree lines that quietly change the set of valid pairs