LeetCode 220: Contains Duplicate III

A clear explanation of checking nearby indices with nearby values using a sliding window and bucket hashing.

leetcodearrayhash-mapbucket-sortsliding-window

Problem Restatement

We are given an integer array nums and two integers:

indexDiff
valueDiff

We need to return True if there are two different indices i and j such that:

i != j
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff

Otherwise, return False.

The official problem asks for a pair of distinct indices whose index distance is at most indexDiff and whose value difference is at most valueDiff. Constraints include 2 <= nums.length <= 10^5, 1 <= indexDiff <= nums.length, and 0 <= valueDiff <= 10^9.

Input and Output

Item Meaning
Input Integer array nums, integer indexDiff, integer valueDiff
Output Boolean
Index condition abs(i - j) <= indexDiff
Value condition abs(nums[i] - nums[j]) <= valueDiff
Distinct indices i != j

Example function shape:

def containsNearbyAlmostDuplicate(
    nums: list[int],
    indexDiff: int,
    valueDiff: int,
) -> bool:
    ...

Examples

Example 1:

nums = [1, 2, 3, 1]
indexDiff = 3
valueDiff = 0

Choose indices 0 and 3.

abs(0 - 3) = 3
abs(1 - 1) = 0

Both conditions are satisfied.

Answer:

True

Example 2:

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

Duplicates exist, but equal values are too far apart by index.

Nearby values also differ too much.

Answer:

False

First Thought: Check Nearby Pairs

A direct method is to check every pair whose index distance is at most indexDiff.

class Solution:
    def containsNearbyAlmostDuplicate(
        self,
        nums: list[int],
        indexDiff: int,
        valueDiff: int,
    ) -> bool:
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, min(n, i + indexDiff + 1)):
                if abs(nums[i] - nums[j]) <= valueDiff:
                    return True

        return False

This is correct, but it may be too slow.

Problem With Brute Force

For each index, we may check up to indexDiff later indices.

The time complexity is:

O(n * indexDiff)

Since n can be 10^5, this can be too large.

We need a faster way to check whether the current value is close to any value in the last indexDiff positions.

Key Insight: Sliding Window by Index

The index condition says:

abs(i - j) <= indexDiff

When scanning from left to right, for current index i, we only care about previous indices:

i - indexDiff, ..., i - 1

So we maintain a sliding window containing at most the last indexDiff values.

Now the problem becomes:

Does the current number have a value-close neighbor inside the window?

Key Insight: Buckets by Value

We need to check:

abs(nums[i] - nums[j]) <= valueDiff

Let:

width = valueDiff + 1

Put each number into a bucket of size width.

For example, if valueDiff = 3, then width = 4.

Buckets:

bucket 0: values 0, 1, 2, 3
bucket 1: values 4, 5, 6, 7
bucket 2: values 8, 9, 10, 11

Any two numbers in the same bucket must differ by at most valueDiff.

Why?

Because bucket width is valueDiff + 1.

So the largest possible distance inside one bucket is valueDiff.

Why Check Neighbor Buckets

Two close values may fall into adjacent buckets.

Example:

valueDiff = 3
width = 4

The values 3 and 4 differ by 1.

But:

3 is in bucket 0
4 is in bucket 1

So for each number, we check:

Bucket Why
Same bucket Always close enough
Previous bucket Could contain close value
Next bucket Could contain close value

No other bucket can contain a close enough value because bucket width is greater than valueDiff.

Handling Negative Numbers

Python floor division works well for bucket IDs.

bucket_id = num // width

For example, with width = 4:

-1 // 4 = -1
-4 // 4 = -1
-5 // 4 = -2

This keeps bucket ranges consistent.

Algorithm

  1. Set width = valueDiff + 1.
  2. Create a dictionary buckets.
  3. Scan nums from left to right.
  4. For current number num:
    • compute bucket_id
    • if same bucket exists, return True
    • if previous bucket exists and value difference is small enough, return True
    • if next bucket exists and value difference is small enough, return True
  5. Put current number into its bucket.
  6. If window size exceeds indexDiff, remove the old number from its bucket.
  7. If no pair is found, return False.

Walkthrough

Use:

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

Then:

width = 4

Process 1 at index 0.

bucket 0 = 1

Process 5 at index 1.

bucket 1 = 5

Check neighbor bucket 0.

abs(5 - 1) = 4

Too large.

Process 9 at index 2.

bucket 2 = 9

Check neighbor bucket 1.

abs(9 - 5) = 4

Too large.

Process 1 at index 3.

Before or after insertion, the window must only contain indices within distance 2.

Index 0 is now too far from index 3, so it is removed.

The new 1 cannot pair with the old 1.

Continue similarly.

No valid pair is found.

Return:

False

Correctness

The sliding window contains only values whose indices are within indexDiff of the current index. Therefore, any pair found inside the window automatically satisfies the index condition.

The bucket width is valueDiff + 1. If two numbers fall in the same bucket, their absolute difference is at most valueDiff, so the value condition is satisfied.

If two numbers are within valueDiff but fall into different buckets, they can only be in neighboring buckets. Buckets farther apart are separated by more than valueDiff.

For each number, the algorithm checks its own bucket and the two neighboring buckets. Therefore, it finds any value in the window that can satisfy the value condition.

If a valid pair exists, when the later index is processed, the earlier index is still in the window and will be found through these bucket checks.

Thus the algorithm returns True exactly when a valid pair exists.

Complexity

Metric Value Why
Time O(n) average Each number is inserted, checked, and removed once
Space O(indexDiff) Buckets store at most the sliding window

Hash map operations are average O(1).

Implementation

class Solution:
    def containsNearbyAlmostDuplicate(
        self,
        nums: list[int],
        indexDiff: int,
        valueDiff: int,
    ) -> bool:
        width = valueDiff + 1
        buckets = {}

        for i, num in enumerate(nums):
            bucket_id = num // width

            if bucket_id in buckets:
                return True

            if bucket_id - 1 in buckets:
                if abs(num - buckets[bucket_id - 1]) <= valueDiff:
                    return True

            if bucket_id + 1 in buckets:
                if abs(num - buckets[bucket_id + 1]) <= valueDiff:
                    return True

            buckets[bucket_id] = num

            if i >= indexDiff:
                old_num = nums[i - indexDiff]
                old_bucket_id = old_num // width
                del buckets[old_bucket_id]

        return False

Code Explanation

The bucket width is:

width = valueDiff + 1

This avoids division by zero when valueDiff = 0.

Create the bucket map:

buckets = {}

Compute the bucket ID:

bucket_id = num // width

If the same bucket already has a value:

if bucket_id in buckets:
    return True

then the current value and that stored value are close enough.

Check the previous bucket:

if bucket_id - 1 in buckets:
    if abs(num - buckets[bucket_id - 1]) <= valueDiff:
        return True

Check the next bucket:

if bucket_id + 1 in buckets:
    if abs(num - buckets[bucket_id + 1]) <= valueDiff:
        return True

Insert the current number:

buckets[bucket_id] = num

Remove the number that falls out of the index window:

if i >= indexDiff:
    old_num = nums[i - indexDiff]
    old_bucket_id = old_num // width
    del buckets[old_bucket_id]

If no valid pair appears:

return False

Ordered Set Idea

Another common approach uses a sorted window.

For current number x, we need any window value in:

[x - valueDiff, x + valueDiff]

With a balanced binary search tree, we can find the first value at least x - valueDiff and check whether it is at most x + valueDiff.

This gives:

Metric Value
Time O(n log indexDiff)
Space O(indexDiff)

Python does not have a built-in balanced ordered set, so the bucket solution is usually preferred for LeetCode Python.

Testing

def run_tests():
    s = Solution()

    assert s.containsNearbyAlmostDuplicate([1, 2, 3, 1], 3, 0) is True
    assert s.containsNearbyAlmostDuplicate([1, 5, 9, 1, 5, 9], 2, 3) is False
    assert s.containsNearbyAlmostDuplicate([1, 0, 1, 1], 1, 2) is True
    assert s.containsNearbyAlmostDuplicate([-1, -1], 1, 0) is True
    assert s.containsNearbyAlmostDuplicate([1, 2], 0, 1) is False
    assert s.containsNearbyAlmostDuplicate([8, 1, 5, 9], 2, 3) is False

    print("all tests passed")

run_tests()
Test Why
[1,2,3,1], 3, 0 Same value within allowed distance
[1,5,9,1,5,9], 2, 3 Duplicates exist but too far
[1,0,1,1], 1, 2 Nearby and value-close pair
[-1,-1], 1, 0 Negative values and exact duplicate
[1,2], 0, 1 Distinct indices cannot have distance 0
[8,1,5,9], 2, 3 Nearby values still too far in value