# LeetCode 220: Contains Duplicate III

## Problem Restatement

We are given an integer array `nums` and two integers:

```python
indexDiff
valueDiff
```

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

```text
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:

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

## Examples

Example 1:

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

Choose indices `0` and `3`.

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

Both conditions are satisfied.

Answer:

```python
True
```

Example 2:

```python
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:

```python
False
```

## First Thought: Check Nearby Pairs

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

```python
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:

```text
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:

```text
abs(i - j) <= indexDiff
```

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

```text
i - indexDiff, ..., i - 1
```

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

Now the problem becomes:

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

## Key Insight: Buckets by Value

We need to check:

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

Let:

```python
width = valueDiff + 1
```

Put each number into a bucket of size `width`.

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

Buckets:

```text
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:

```python
valueDiff = 3
width = 4
```

The values `3` and `4` differ by `1`.

But:

```text
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.

```python
bucket_id = num // width
```

For example, with `width = 4`:

```text
-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:

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

Then:

```python
width = 4
```

Process `1` at index `0`.

```text
bucket 0 = 1
```

Process `5` at index `1`.

```text
bucket 1 = 5
```

Check neighbor bucket `0`.

```text
abs(5 - 1) = 4
```

Too large.

Process `9` at index `2`.

```text
bucket 2 = 9
```

Check neighbor bucket `1`.

```text
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:

```python
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

```python
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:

```python
width = valueDiff + 1
```

This avoids division by zero when `valueDiff = 0`.

Create the bucket map:

```python
buckets = {}
```

Compute the bucket ID:

```python
bucket_id = num // width
```

If the same bucket already has a value:

```python
if bucket_id in buckets:
    return True
```

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

Check the previous bucket:

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

Check the next bucket:

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

Insert the current number:

```python
buckets[bucket_id] = num
```

Remove the number that falls out of the index window:

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

If no valid pair appears:

```python
return False
```

## Ordered Set Idea

Another common approach uses a sorted window.

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

```text
[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

```python
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 |