LeetCode 219 - Contains Duplicate II

The problem asks us to determine whether an array contains two equal values whose indices are close to each other.

leetcodeeasyarrayhash-tablesliding-window

LeetCode Problem 219

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sliding Window

Solution

Problem Understanding

The problem asks us to determine whether an array contains two equal values whose indices are close to each other. More specifically, we need to check if there exist two distinct indices i and j such that:

  • nums[i] == nums[j]
  • abs(i - j) <= k

The array nums contains integers, and k defines the maximum allowed distance between duplicate elements.

In simpler terms, we are looking for a repeated number that appears again within at most k positions from its previous occurrence. If such a pair exists, we return true. Otherwise, we return false.

For example, consider:

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

The value 1 appears at indices 0 and 3. The distance between them is:

abs(0 - 3) = 3

Since 3 <= k, the answer is true.

The constraints are important because they influence which algorithms are feasible:

  • nums.length can be as large as 100000
  • k can also be as large as 100000

A naive quadratic solution that compares every pair of indices would require up to 10^10 operations in the worst case, which is far too slow. This strongly suggests that we need a linear or near-linear solution.

Several edge cases are worth identifying early:

  • k = 0, duplicates are never allowed because indices must be distinct and their distance must be at most 0
  • Arrays with no duplicates at all
  • Duplicates that exist but are farther apart than k
  • Negative numbers, since values can range down to -10^9
  • Very large arrays where efficiency matters

The problem guarantees that the input array is non-empty, so we do not need to handle a completely empty array.

Approaches

Brute Force Approach

The most straightforward solution is to compare every pair of indices (i, j) where i < j.

For each pair:

  • Check whether nums[i] == nums[j]
  • If they are equal, compute abs(i - j)
  • Return true if the distance is at most k

This approach is correct because it exhaustively examines every possible pair of indices. If a valid duplicate pair exists, the algorithm will eventually find it.

However, the time complexity is extremely poor. For an array of size n, there are approximately:

$\frac{n(n-1)}{2}$

pairs to examine.

That leads to O(n²) time complexity, which is too slow for n = 100000.

Optimal Approach

The key observation is that we do not actually need to compare every pair of indices.

Instead, when processing an element, we only care whether we have seen the same value recently, within the last k indices.

A hash map provides exactly what we need:

  • Store each number along with its most recent index
  • As we iterate through the array, check whether the current number already exists in the map
  • If it does, compute the distance between indices
  • If the distance is at most k, return true

This works because the most recent occurrence of a value is always the best candidate for satisfying the distance condition.

Using a hash map allows each lookup and insertion to be performed in approximately constant time, producing a linear overall solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compares every pair of indices
Optimal O(n) O(n) Uses a hash map to track recent indices

Algorithm Walkthrough

  1. Create a hash map called last_seen.

The hash map will store each number as the key and the most recent index where that number appeared as the value. 2. Iterate through the array using both index and value.

At each step, we examine the current number and determine whether it has appeared before. 3. Check whether the current number already exists in the hash map.

If it does not exist, this is the first occurrence of the number, so we simply record its index. 4. If the number exists, retrieve its previous index.

Compute the distance between the current index and the previous index:

$|i-j|$ 5. Compare the distance with k.

If the distance is less than or equal to k, we immediately return true because we found a valid nearby duplicate. 6. Update the hash map with the current index.

Even if the number was already present, we overwrite the old index because the most recent occurrence is the most useful one for future comparisons. 7. If the loop completes without finding a valid pair, return false.

Why it works

The algorithm maintains an important invariant: for every value encountered so far, the hash map stores its most recent index.

When we encounter a duplicate value, the closest previous occurrence is always the most recent one. If even that closest occurrence is farther than k, then all earlier occurrences are even farther away and cannot satisfy the condition.

Because every element is checked against its nearest previous duplicate candidate, the algorithm correctly detects whether a valid nearby duplicate exists.

Python Solution

from typing import List

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

        for index, value in enumerate(nums):
            if value in last_seen:
                previous_index = last_seen[value]

                if index - previous_index <= k:
                    return True

            last_seen[value] = index

        return False

The implementation begins by creating a dictionary named last_seen. This dictionary maps each number to the latest index where it appeared.

The loop uses enumerate(nums) so that both the current index and current value are available during iteration.

For every value:

  • The code first checks whether the value already exists in the dictionary.
  • If it does, the previous index is retrieved.
  • The difference between the current index and previous index is computed.
  • If that difference is less than or equal to k, the function immediately returns True.

After the check, the dictionary is updated with the current index. This ensures the dictionary always contains the most recent occurrence of each number.

If the loop finishes without returning True, then no valid nearby duplicate exists, so the function returns False.

Go Solution

func containsNearbyDuplicate(nums []int, k int) bool {
	lastSeen := make(map[int]int)

	for index, value := range nums {
		if previousIndex, exists := lastSeen[value]; exists {
			if index-previousIndex <= k {
				return true
			}
		}

		lastSeen[value] = index
	}

	return false
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used to store the most recent index for each value. Go maps return two values during lookup:

value, exists := map[key]

The exists boolean allows us to determine whether the key was already present.

There are no integer overflow concerns because the index differences are well within Go's integer range given the problem constraints.

Go slices are dynamically sized views over arrays, so iterating through nums with range is efficient and idiomatic.

Worked Examples

Example 1

nums = [1,2,3,1], k = 3
Index Value last_seen Before Action Result
0 1 {} Store 1 → 0 Continue
1 2 {1:0} Store 2 → 1 Continue
2 3 {1:0, 2:1} Store 3 → 2 Continue
3 1 {1:0, 2:1, 3:2} Distance = 3 - 0 = 3 Return true

The duplicate 1 appears within distance 3, so the answer is true.

Example 2

nums = [1,0,1,1], k = 1
Index Value last_seen Before Action Result
0 1 {} Store 1 → 0 Continue
1 0 {1:0} Store 0 → 1 Continue
2 1 {1:0, 0:1} Distance = 2 - 0 = 2 Continue
3 1 {1:2, 0:1} Distance = 3 - 2 = 1 Return true

The algorithm updates the stored index for 1 from 0 to 2. This is important because the most recent occurrence provides the smallest distance.

Example 3

nums = [1,2,3,1,2,3], k = 2
Index Value Previous Index Distance Valid?
0 1 None - No
1 2 None - No
2 3 None - No
3 1 0 3 No
4 2 1 3 No
5 3 2 3 No

Every duplicate is farther than k, so the final answer is false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once with constant-time hash map operations
Space O(n) The hash map may store up to all unique elements

The algorithm performs a single pass through the array. Every lookup and insertion into the hash map is approximately O(1) on average, so the total running time grows linearly with the size of the array.

The extra space comes from storing indices for unique values. In the worst case, when all numbers are distinct, the hash map contains n entries.

Test Cases

from typing import List

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

        for index, value in enumerate(nums):
            if value in last_seen:
                if index - last_seen[value] <= k:
                    return True

            last_seen[value] = index

        return False

solution = Solution()

assert solution.containsNearbyDuplicate([1, 2, 3, 1], 3) is True
# duplicate within allowed distance

assert solution.containsNearbyDuplicate([1, 0, 1, 1], 1) is True
# adjacent duplicate

assert solution.containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2) is False
# duplicates exist but are too far apart

assert solution.containsNearbyDuplicate([1], 1) is False
# single element array

assert solution.containsNearbyDuplicate([1, 1], 0) is False
# k = 0 means distinct indices cannot satisfy condition

assert solution.containsNearbyDuplicate([1, 1], 1) is True
# smallest valid duplicate case

assert solution.containsNearbyDuplicate([-1, -2, -3, -1], 3) is True
# negative numbers

assert solution.containsNearbyDuplicate([1, 2, 3, 4, 5], 2) is False
# no duplicates at all

assert solution.containsNearbyDuplicate([99, 99, 99], 1) is True
# repeated duplicates

assert solution.containsNearbyDuplicate([1, 2, 1], 1) is False
# duplicate exists but exceeds k

assert solution.containsNearbyDuplicate([1, 2, 3, 4, 1], 4) is True
# duplicate exactly at distance k

Test Summary

Test Why
[1,2,3,1], k=3 Basic valid duplicate case
[1,0,1,1], k=1 Adjacent duplicate validation
[1,2,3,1,2,3], k=2 Duplicates exist but are too far apart
[1], k=1 Minimum array size
[1,1], k=0 Verifies zero-distance constraint
[1,1], k=1 Smallest successful duplicate case
[-1,-2,-3,-1], k=3 Handles negative integers
[1,2,3,4,5], k=2 No duplicates present
[99,99,99], k=1 Multiple repeated duplicates
[1,2,1], k=1 Duplicate outside valid range
[1,2,3,4,1], k=4 Distance exactly equal to k

Edge Cases

One important edge case occurs when k = 0. Since the indices must be distinct, no two different indices can have a distance of zero. Even if duplicates exist, the answer must always be false. The implementation handles this naturally because any duplicate pair will have a positive index difference, which cannot satisfy <= 0.

Another important case is when duplicates exist but are farther apart than k. A naive implementation might incorrectly return true immediately after seeing any duplicate value. For example:

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

The duplicate 1 values are distance 3 apart, so the answer should be false. The algorithm explicitly checks the index difference before returning.

A third important edge case involves repeated duplicates. Consider:

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

If the algorithm failed to update the stored index after each occurrence, it would compare against outdated positions and might miss a valid nearby duplicate. By always storing the most recent index, the implementation correctly detects the duplicate pair at indices 2 and 3.

Another subtle case is arrays with all unique elements. In that situation, the hash map grows throughout the iteration, but no duplicate condition is ever triggered. The algorithm correctly finishes the loop and returns false.