Contains Duplicate II (LC 219)

Pattern: Sliding Window + HashSet
Difficulty: Easy
Key Concept: Maintain a window of k elements using a HashSet to detect duplicates

Problem Statement

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.

• Input: int[] nums, int k
• Output: boolean

---

1. Algorithm & Pseudocode

FUNCTION containsNearbyDuplicate(nums, k):
    SET window = empty HashSet
    
    FOR i = 0 TO nums.length - 1:
        IF window contains nums[i]:
            RETURN true
        
        window.add(nums[i])
        
        IF window.size() > k:
            window.remove(nums[i - k])
    
    RETURN false

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Step 1: We maintain a “window” of at most k elements using a HashSet.
• Step 2: For each new element, check if it already exists in the window (meaning a duplicate within distance k).
• Step 3: Add the element to the window.
• Step 4: If the window exceeds size k, remove the oldest element (the one that’s now too far away).
• Why HashSet? It gives O(1) lookup for checking duplicates instead of scanning the window.

---

3. The Dry Run

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

Step	i	nums[i]	Window (before)	Contains?	Window (after)	Action
1	0	1	{}	No	{1}	Add 1
2	1	2	{1}	No	{1, 2}	Add 2
3	2	3	{1, 2}	No	{1, 2, 3}	Add 3
4	3	1	{1, 2, 3}	Yes!	-	Return true

Result: true (nums[0] == nums[3], distance = 3 <= k)

---

4. Java Solution

Brute Force

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j <= Math.min(i + k, nums.length - 1); j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }
}

Optimal

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> window = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (!window.add(nums[i])) return true;
            
            if (window.size() > k) {
                window.remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

---

5. The “Java vs. Others” Edge

• HashSet.add() returns boolean: Returns false if element already exists. This is a powerful one-liner trick! if (!set.add(x)) checks AND adds in one operation.
• In C++: unordered_set::insert() returns a pair<iterator, bool> where .second is the success flag. More verbose.
• In Python: Sets don’t have this return value. You’d use if x in window first, then window.add(x).
• window.remove(nums[i - k]): HashSet.remove() is O(1) average. No need for an ordered data structure since we only care about presence, not position.
• Autoboxing: nums[i] is int but HashSet<Integer> stores Integer objects. Java auto-boxes. For very large arrays, this adds overhead vs primitive-based sets (like Eclipse Collections IntHashSet).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n * k)	O(1)	Check next k elements for each
Sliding Window + HashSet	O(n)	O(k)	Window of at most k elements