219. Contains Duplicate II - Explanation

Problem Link

Description

You are given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k, otherwise return false.

Example 1:

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

Output: true

Example 2:

Input: nums = [2,1,2], k = 1

Output: false

Constraints:

• 1 <= nums.length <= 100,000
• -1,000,000,000 <= nums[i] <= 1,000,000,000
• 0 <= k <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

The simplest approach is to check every pair of elements. For each element, we look at all elements within distance k and check if any of them are equal. This guarantees finding a duplicate if one exists within the required distance.

Algorithm

1. Iterate through each index L from 0 to n-1.
2. For each L, iterate through index R from L+1 to min(n-1, L+k).
3. If nums[L] == nums[R], return true.
4. If no such pair is found, return false.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        for L in range(len(nums)):
            for R in range(L + 1, min(len(nums), L + k + 1)):
                if nums[L] == nums[R]:
                    return True
        return False

Time & Space Complexity

• Time complexity: $O(n * min(n, k))$
• Space complexity: $O(1)$

Where $n$ is the size of the array $nums$ and $k$ is the maximum distance between two equal numbers.

---

2. Hash Map

Intuition

Instead of checking all pairs, we can store the most recent index of each value in a hash map. When we encounter a value, we check if it appeared before and if the distance to its last occurrence is within k. This gives us O(1) lookup time for duplicates.

Algorithm

1. Create a hash map to store each value's most recent index.
2. Iterate through the array with index i.
3. If nums[i] exists in the map and i - map[nums[i]] <= k, return true.
4. Update map[nums[i]] = i (store the current index).
5. If no valid pair is found, return false.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        mp = {}

        for i in range(len(nums)):
            if nums[i] in mp and i - mp[nums[i]] <= k:
                return True
            mp[nums[i]] = i

        return False

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $k$ is the maximum distance between two equal numbers.

---

3. Hash Set

Intuition

We only need to check for duplicates within a sliding window of size k. Using a hash set, we maintain exactly the elements in the current window. If a new element already exists in the set, we found a duplicate within distance k. We slide the window by removing the leftmost element when the window exceeds size k.

Algorithm

1. Create an empty hash set to represent the sliding window.
2. Use two pointers L and R, with R iterating through the array.
3. If the window size R - L exceeds k, remove nums[L] from the set and increment L.
4. If nums[R] is already in the set, return true.
5. Add nums[R] to the set.
6. If no duplicate is found, return false.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        L = 0

        for R in range(len(nums)):
            if R - L > k:
                window.remove(nums[L])
                L += 1
            if nums[R] in window:
                return True
            window.add(nums[R])

        return False

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(min(n, k))$

Where $n$ is the size of the array $nums$ and $k$ is the maximum distance between two equal numbers.

---

Common Pitfalls

Off-by-One Error in Distance Check

The condition requires the distance to be "at most k", meaning abs(i - j) <= k, not < k. Using strict inequality will miss valid pairs that are exactly k positions apart.

# Wrong: Using strict inequality
if nums[i] in mp and i - mp[nums[i]] < k:  # Misses distance == k

# Correct: Use <= for "at most k"
if nums[i] in mp and i - mp[nums[i]] <= k:

Storing All Indices Instead of Most Recent

The hash map only needs to store the most recent index for each value. Storing all indices wastes memory and complicates the logic. Since we iterate left to right, we only care about the closest previous occurrence.