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:

nums[i] == nums[j]

and:

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

Example function shape:

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

Examples

Example 1:

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

The value 1 appears at indices 0 and 3.

Distance:

abs(0 - 3) = 3

Since 3 <= k, the answer is:

True

Example 2:

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

The value 1 appears at indices 2 and 3.

Distance:

abs(2 - 3) = 1

Answer:

True

Example 3:

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

Duplicates exist, but none are close enough.

The repeated 1s are at indices 0 and 3.

Distance:

3

But 3 > 2.

Answer:

False

First Thought: Check Every Pair

The direct method is to compare every pair of indices.

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:

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:

value -> latest index

When we see the same value again, check:

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:

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

Start:

last_seen = {}

Process index 0, value 1:

last_seen = {1: 0}

Process index 1, value 2:

last_seen = {1: 0, 2: 1}

Process index 2, value 3:

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

Process index 3, value 1.

Previous index of 1 is 0.

Distance:

3 - 0 = 3

Since 3 <= k, return:

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

Hash Map Implementation

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:

last_seen = {}

Scan with index and value:

for i, num in enumerate(nums):

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

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

Update the latest index:

last_seen[num] = i

If no valid pair was found:

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:

i - k to i - 1

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

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

Testing

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()