This is a popular interview question because it tests the ability to optimize a search operation within a localized range of an array.

Brute Force Approach for Contains Duplicate II

The naive approach involves checking every possible pair of indices $(i, j)$ in the array to see if they satisfy both conditions: value equality and index proximity.

We iterate through each element at index $i$ and then iterate through subsequent elements at index $j$ where $i < j \le i + k$. For each pair, we check if nums[i] == nums[j].

Pseudo-code:

text
for i from 0 to length(nums) - 1:
    for j from i + 1 to min(i + k, length(nums) - 1):
        if nums[i] == nums[j]:
            return true
return false

Time Complexity Analysis: The outer loop runs $n$ times. The inner loop runs up to $k$ times. In the worst case (where $k$ is close to $n$), this results in a time complexity of $O(n \cdot k)$ or roughly $O(n^2)$.

Why it fails: The constraints allow nums.length up to $10^5$ and $k$ up to $10^5$. An $O(n^2)$ solution will perform approximately $10^{10}$ operations in the worst case, leading to a Time Limit Exceeded (TLE) error. We need a linear time solution.

Core Insight for Contains Duplicate II

The brute force approach is inefficient because it repeatedly scans the same elements to check for duplicates. For every index $i$, we look ahead at the next $k$ elements. When we move to $i+1$, we look at almost the same set of elements again.

The key insight is to maintain a "memory" of the elements currently within the valid distance $k$. As we iterate through the array with a pointer right, we are effectively considering a window ending at right.

To satisfy the condition $|i - j| \le k$, we only care about elements in the range [right - k, right - 1]. By maintaining a Hash Set representing this sliding window, we can check if nums[right] exists in the set in $O(1)$ time.

The pattern enforces a strict constraint: The window size must not exceed $k$.

1. As we expand right, we add elements to our window (Hash Set).
2. If the window size exceeds $k$ (i.e., the distance between left and right is greater than $k$), we shrink the window from the left by removing nums[left] from the set.
3. This ensures that at any point, the set only contains numbers from the previous $k$ indices.

Visual Description: Imagine a window frame that can hold at most $k$ numbers sliding across the array from left to right. As the frame moves one step forward to include a new number, the oldest number (if the frame is full) drops out of the back. We simply check if the new number entering the frame matches any number currently inside it.

Execution Flow

Let's trace the algorithm with nums = [1, 2, 3, 1] and k = 3.

1. Initialize: window = {}, left = 0.
2. Index right = 0: val = 1
   • Window size is 0 (valid).
   • 1 is not in window.
   • Add 1. window = {1}.
3. Index right = 1: val = 2
   • Window size is 1 (valid).
   • 2 is not in window.
   • Add 2. window = {1, 2}.
4. Index right = 2: val = 3
   • Window size is 2 (valid).
   • 3 is not in window.
   • Add 3. window = {1, 2, 3}.
5. Index right = 3: val = 1
   • Window size is 3 (valid).
   • 1 IS in window.
   • Return True.

Now consider nums = [1, 2, 3, 1, 2, 3] and k = 2. ...

• When right reaches index 3 (val = 1):
  • Current window indices effectively: [1, 2] (values {2, 3}).
  • The element at index 0 (1) was removed because index $3 - 0 > 2$.
  • 1 is not in {2, 3}. Add 1.
• This ensures we only match within distance $k$.

Proof of Correctness

The algorithm relies on the invariant that the Hash Set contains exactly the elements from the subarray nums[max(0, right-k) ... right-1].

• Completeness: If a duplicate pair $(i, j)$ exists with $j - i \le k$, then when the algorithm reaches index $j$ (right = j), the index $i$ will satisfy $i \ge j - k$. Therefore, nums[i] will still be present in the Hash Set. The check window.contains(nums[right]) will correctly return true.
• Soundness: The algorithm removes nums[left] as soon as right - left > k. Thus, if window.contains(nums[right]) returns true, the matching element must be at an index $i$ such that right - i <= k. This satisfies the problem constraints.

Reference Implementation

C++ Solution for LeetCode 219

cpp
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        // Hash set to store elements in the current window of size k
        unordered_set<int> window;
        int left = 0;
        
        for (int right = 0; right < nums.size(); ++right) {
            // If window size exceeds k, shrink from the left
            if (right - left > k) {
                window.erase(nums[left]);
                left++;
            }
            
            // Check if current element exists in the window
            if (window.count(nums[right])) {
                return true;
            }
            
            // Add current element to the window
            window.insert(nums[right]);
        }
        
        return false;
    }
};

Java Solution for LeetCode 219

java
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // Hash set to store elements in the current window of size k
        Set<Integer> window = new HashSet<>();
        int left = 0;
        
        for (int right = 0; right < nums.length; right++) {
            // If window size exceeds k, shrink from the left
            if (right - left > k) {
                window.remove(nums[left]);
                left++;
            }
            
            // Check if current element exists in the window
            if (window.contains(nums[right])) {
                return true;
            }
            
            // Add current element to the window
            window.add(nums[right]);
        }
        
        return false;
    }
}

Python Solution for LeetCode 219

python
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # Hash set to store elements in the current window of size k
        window = set()
        left = 0
        
        for right in range(len(nums)):
            # If window size exceeds k, shrink from the left
            if right - left > k:
                window.remove(nums[left])
                left += 1
            
            # Check if current element exists in the window
            if nums[right] in window:
                return True
            
            # Add current element to the window
            window.add(nums[right])
            
        return False