LeetCode 219: Contains Duplicate II - All Solutions Explained

Problem Statement

The Contains Duplicate II problem (LeetCode 219) is an easy-level array challenge that extends Contains Duplicate (LeetCode 217) by adding a distance constraint. Given an integer array nums and an integer k, return true if there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k.

Copy codeInput: nums = [1,2,3,1], k = 3
Output: true
Explanation: nums[0] == nums[3] and abs(0-3) <= 3

Input: nums = [1,0,1,1], k = 1
Output: true
Explanation: nums[2] == nums[3] and abs(2-3) <= 1

Explanation of the Best Solution

This approach uses a hash map to track the most recent index of each value while maintaining a sliding window:

1. Initialize Hash Map: To store value → last index mappings
2. Iterate Through Array:
3. For each number, check if it exists in the map
4. If found and the index difference ≤ k, return true
5. Update the map with the current index (overwriting previous)
6. Final Check: If loop completes without finding valid duplicates, return false

Step-by-Step Example

For nums = [1,2,3,1], k = 3: 1. i=0: map={1:0} 2. i=1: map={1:0, 2:1} 3. i=2: map={1:0, 2:1, 3:2} 4. i=3: Found 1 at index 0 → abs(3-0)=3 ≤ 3 → return true

Python Code (Hash Map Solution)

Copy codeclass Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        index_map = {}
        for i, num in enumerate(nums):
            if num in index_map and i - index_map[num] <= k:
                return True
            index_map[num] = i  # Always update to latest index
        return False

# Test cases
print(Solution().containsNearbyDuplicate([1,2,3,1], 3))  # True
print(Solution().containsNearbyDuplicate([1,0,1,1], 1))  # True
print(Solution().containsNearbyDuplicate([1,2,3,4], 1))  # False

Complexity

• Time Complexity: O(n) - Single pass through array
• Space Complexity: O(min(n,k)) - Stores at most k+1 elements
• Optimizations: Early termination when duplicate found

Why It's the Best

• Optimal O(n) time complexity
• Efficient space usage (only stores recent indices)
• Simple and clean implementation
• Standard approach for sliding window problems

Solution 2: Sliding Window with Hash Set (Alternative)

Explanation

This approach maintains a hash set of the current window of k+1 elements:

1. Initialize Hash Set: To store elements in current window
2. Iterate Through Array:
3. If current element exists in set → return true
4. Add current element to set
5. Remove element that fell out of window (when i > k)
6. Final Check: Return false if no duplicates found

Step-by-Step Example

For nums = [1,0,1,1], k = 1: 1. i=0: set={1} 2. i=1: set={1,0} 3. i=2: Found 1 in set → return true

Python Code (Hash Set Solution)

Copy codeclass 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 i >= k:  # Maintain window size of k+1
                window.remove(nums[i - k])
        return False

# Test cases
print(Solution().containsNearbyDuplicate([1,2,3,1], 3))  # True
print(Solution().containsNearbyDuplicate([1,0,1,1], 1))  # True

Complexity

• Time Complexity: O(n) - Each element added/removed once
• Space Complexity: O(min(n,k)) - Window size limited to k+1
• Best for: When k is relatively small

Pros and Cons

• Pros: Explicit window maintenance
• Cons: More operations than hash map solution
• Variation: Can use OrderedDict for LRU cache implementation

Solution 3: Brute Force (Naive Approach)

Explanation

The straightforward approach compares each element with the next k elements:

1. Nested Loops:
2. Outer loop through each element
3. Inner loop checks next k elements
4. Early Termination: Return true if any duplicate found
5. Final Check: Return false if no duplicates found

Python Code (Brute Force Solution)

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

# Test cases
print(Solution().containsNearbyDuplicate([1,2,3,1], 3))  # True
print(Solution().containsNearbyDuplicate([1,2,3,4], 1))  # False

Complexity

• Time Complexity: O(n×k) - Worst case when k ≈ n becomes O(n²)
• Space Complexity: O(1) - No additional storage
• When to Use: Only for very small n and k

Edge Cases to Consider

• k = 0 → always false (indices must be distinct)
• k ≥ n → equivalent to Contains Duplicate
• All elements same → true for any k > 0
• Large input with no duplicates → must handle efficiently
• Negative numbers → all solutions work correctly

Final Thoughts

• Hash Map: Best for most cases (optimal time/space)
• Hash Set: Good alternative with explicit window
• Brute Force: Only for understanding the problem
• Key Insight: Sliding window optimization is crucial

For further practice, try similar problems like Contains Duplicate III (LeetCode 220) or Longest Substring Without Repeating Characters (LeetCode 3).