Contains Duplicate II

LeetCode 219: Contains Duplicate II Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a Hash Set to maintain a sliding window of the most recent $k$ elements, allowing for $O(1)$ duplicate detection.

The LeetCode 219 problem, "Contains Duplicate II," asks us to determine if an integer array nums contains any duplicate elements located within a specific proximity. specifically, we need to return true if there exist two distinct indices $i$ and $j$ such that nums[i] == nums[j] and the absolute difference between the indices is at most $k$ ($|i - j| \le k$). If no such pair exists, we return false.

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:

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.

Algorithm Strategy: Sliding Window Patterns

We utilize the Sliding Window - Variable Size (Condition-Based) strategy combined with a Hash Set for efficient lookups.

1. State Management: We maintain a window (Hash Set) that stores the unique elements found in the current range $[left, right]$.
2. Expansion: We iterate through the array using a right pointer (from $0$ to $n-1$).
3. Constraint Enforcement: Before processing nums[right], we check if the current window size violates the condition (distance $> k$). If right - left > k (or simply if the window size exceeds $k$), we remove the element at nums[left] from the set and increment left.
4. Check and Update:
   • Check if nums[right] is already in the window. If it is, we have found a duplicate within distance $k$, so we return true.
   • If not, add nums[right] to the window.
5. Termination: If the loop completes without finding a duplicate, return false.

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.

Pattern Reuse Notes

The Sliding Window - Variable Size pattern is versatile. Understanding how to maintain window invariants (like "size $\le k$" or "unique characters") applies directly to:

• LeetCode 3: Longest Substring Without Repeating Characters: Instead of a fixed max size, the window expands until a duplicate is found, then shrinks to restore uniqueness.
• LeetCode 76: Minimum Window Substring: The window expands to satisfy a condition (contain all chars of T) and shrinks to minimize length.
• LeetCode 209: Minimum Size Subarray Sum: The window shrinks from the left as long as the sum condition ($\ge target$) is met to find the minimal length.
• LeetCode 424: Longest Repeating Character Replacement: The window grows and shrinks based on the count of the dominant character plus $k$ replacements.

Reference Implementation

C++ Solution for LeetCode 219

1class Solution {
2public:
3    bool containsNearbyDuplicate(vector<int>& nums, int k) {
4        // Hash set to store elements in the current window of size k
5        unordered_set<int> window;
6        int left = 0;
7        
8        for (int right = 0; right < nums.size(); ++right) {
9            // If window size exceeds k, shrink from the left
10            if (right - left > k) {
11                window.erase(nums[left]);
12                left++;
13            }
14            
15            // Check if current element exists in the window
16            if (window.count(nums[right])) {
17                return true;
18            }
19            
20            // Add current element to the window
21            window.insert(nums[right]);
22        }
23        
24        return false;
25    }
26};

Java Solution for LeetCode 219

1class Solution {
2    public boolean containsNearbyDuplicate(int[] nums, int k) {
3        // Hash set to store elements in the current window of size k
4        Set<Integer> window = new HashSet<>();
5        int left = 0;
6        
7        for (int right = 0; right < nums.length; right++) {
8            // If window size exceeds k, shrink from the left
9            if (right - left > k) {
10                window.remove(nums[left]);
11                left++;
12            }
13            
14            // Check if current element exists in the window
15            if (window.contains(nums[right])) {
16                return true;
17            }
18            
19            // Add current element to the window
20            window.add(nums[right]);
21        }
22        
23        return false;
24    }
25}

Python Solution for LeetCode 219

1class Solution:
2    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
3        # Hash set to store elements in the current window of size k
4        window = set()
5        left = 0
6        
7        for right in range(len(nums)):
8            # If window size exceeds k, shrink from the left
9            if right - left > k:
10                window.remove(nums[left])
11                left += 1
12            
13            # Check if current element exists in the window
14            if nums[right] in window:
15                return True
16            
17            # Add current element to the window
18            window.add(nums[right])
19            
20        return False