# LeetCode 219: Contains Duplicate II

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

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

```text
nums[i] == nums[j]
```

and:

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

Otherwise, return `False`.

The official statement asks whether two distinct indices have equal values and index distance at most `k`. Constraints include `1 <= nums.length <= 10^5`, `-10^9 <= nums[i] <= 10^9`, and `0 <= k <= 10^5`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `k` |
| Output | Boolean |
| `True` | Duplicate values exist within distance `k` |
| `False` | No such pair exists |
| Distinct indices | `i` and `j` must be different |

Example function shape:

```python
def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3, 1]
k = 3
```

The value `1` appears at indices `0` and `3`.

Distance:

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

Since `3 <= k`, the answer is:

```python
True
```

Example 2:

```python
nums = [1, 0, 1, 1]
k = 1
```

The value `1` appears at indices `2` and `3`.

Distance:

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

Answer:

```python
True
```

Example 3:

```python
nums = [1, 2, 3, 1, 2, 3]
k = 2
```

Duplicates exist, but none are close enough.

The repeated `1`s are at indices `0` and `3`.

Distance:

```text
3
```

But `3 > 2`.

Answer:

```python
False
```

## First Thought: Check Every Pair

The direct method is to compare every pair of indices.

```python
class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        n = len(nums)

        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j] and j - i <= k:
                    return True

        return False
```

This is correct, but too slow.

## Problem With Brute Force

The array can contain up to `10^5` elements.

Checking every pair may take:

```text
O(n^2)
```

That is too large.

We need to remember where each value last appeared.

## Key Insight: Store the Last Index

When scanning from left to right, suppose the current index is `i`.

If we have seen `nums[i]` before at index `j`, then the nearest previous duplicate is the most recent index for that value.

So we store:

```text
value -> latest index
```

When we see the same value again, check:

```text
i - previous_index <= k
```

If yes, return `True`.

If no, update the latest index.

Why update?

Because the latest occurrence gives the best chance of being close to a future index.

## Algorithm

1. Create an empty dictionary `last_seen`.
2. Scan the array with index `i` and value `num`.
3. If `num` exists in `last_seen`:
   - check whether `i - last_seen[num] <= k`
   - if yes, return `True`
4. Set `last_seen[num] = i`.
5. If the scan finishes, return `False`.

## Walkthrough

Use:

```python
nums = [1, 2, 3, 1]
k = 3
```

Start:

```python
last_seen = {}
```

Process index `0`, value `1`:

```python
last_seen = {1: 0}
```

Process index `1`, value `2`:

```python
last_seen = {1: 0, 2: 1}
```

Process index `2`, value `3`:

```python
last_seen = {1: 0, 2: 1, 3: 2}
```

Process index `3`, value `1`.

Previous index of `1` is `0`.

Distance:

```text
3 - 0 = 3
```

Since `3 <= k`, return:

```python
True
```

## Correctness

The dictionary `last_seen` stores the latest index where each value appeared before the current index.

When the algorithm processes `nums[i]`, any valid pair ending at `i` must use a previous index where the same value appeared.

Among all previous occurrences of the same value, the latest one has the smallest distance to `i`.

Therefore, if the latest previous occurrence is farther than `k`, then all earlier occurrences are also farther than `k`.

If the latest previous occurrence is within distance `k`, the algorithm returns `True`, which is correct because it has found two distinct indices with equal values and distance at most `k`.

If the algorithm finishes without returning `True`, then no index has a previous equal value close enough, so no valid pair exists.

Thus the algorithm is correct.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each element is processed once |
| Space | `O(n)` | The dictionary may store many distinct values |

## Hash Map Implementation

```python
class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        last_seen = {}

        for i, num in enumerate(nums):
            if num in last_seen and i - last_seen[num] <= k:
                return True

            last_seen[num] = i

        return False
```

## Code Explanation

Create a dictionary:

```python
last_seen = {}
```

Scan with index and value:

```python
for i, num in enumerate(nums):
```

If the number appeared before and the distance is small enough:

```python
if num in last_seen and i - last_seen[num] <= k:
    return True
```

Update the latest index:

```python
last_seen[num] = i
```

If no valid pair was found:

```python
return False
```

## Sliding Window Set Version

Another way is to keep only the previous `k` values in a set.

At index `i`, the set represents values from indices:

```text
i - k to i - 1
```

If `nums[i]` already exists in the set, then it has appeared within distance `k`.

```python
class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        window = set()

        for i, num in enumerate(nums):
            if num in window:
                return True

            window.add(num)

            if len(window) > k:
                window.remove(nums[i - k])

        return False
```

This also runs in `O(n)` time.

## Sliding Window Explanation

For each index, we check only nearby previous values.

The set never contains more than `k` elements.

When the window becomes too large, remove the value that is now more than `k` positions behind.

The hash map version is slightly simpler to reason about. The window version uses `O(k)` space.

## Complexity Comparison

| Method | Time | Space |
|---|---:|---:|
| Hash map latest index | `O(n)` | `O(n)` |
| Sliding window set | `O(n)` | `O(k)` |
| Brute force | `O(n^2)` | `O(1)` |

## Testing

```python
def run_tests():
    s = Solution()

    assert s.containsNearbyDuplicate([1, 2, 3, 1], 3) is True
    assert s.containsNearbyDuplicate([1, 0, 1, 1], 1) is True
    assert s.containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2) is False
    assert s.containsNearbyDuplicate([1, 2, 3, 1], 2) is False
    assert s.containsNearbyDuplicate([1, 1], 0) is False
    assert s.containsNearbyDuplicate([99, 99], 1) is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,2,3,1], k = 3` | Duplicate exactly at distance `k` |
| `[1,0,1,1], k = 1` | Nearby duplicate at adjacent indices |
| `[1,2,3,1,2,3], k = 2` | Duplicates exist but too far |
| `[1,2,3,1], k = 2` | Same value outside window |
| `[1,1], k = 0` | Distinct indices cannot have distance `0` |
| `[99,99], k = 1` | Small positive case |