5. Contains Duplicate

🔗 LeetCode Problem: 217. Contains Duplicate
📊 Difficulty: Easy
🏷️ Topics: Array, Hash Table, Sorting

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

Input: nums = [1,2,3,1]
Output: true
Explanation: 1 appears twice

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: All elements are distinct

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Explanation: Multiple duplicates exist

Constraints: - 1 <= nums.length <= 10^5 - -10^9 <= nums[i] <= 10^9

---

🎨 Visual Understanding

The Problem Visualized

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

Array scan:
Index:  0   1   2   3
Value:  1   2   3   1
        ↓           ↓
        └───────────┘
        Same value! Duplicate found!

Result: true

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

Array scan:
Index:  0   1   2   3
Value:  1   2   3   4
        ↓   ↓   ↓   ↓
        All different values

Result: false

Different Approaches Comparison

Approach 1: Brute Force (Compare all pairs)
[1, 2, 3, 1]
 ↓
 Compare 1 with: 2, 3, 1 ← Found match at index 3!

Time: O(n²) - nested loops
Space: O(1)

Approach 2: Sorting
[1, 2, 3, 1]
    ↓ Sort
[1, 1, 2, 3] ← Duplicates are now adjacent!
 ↓ ↓
Check neighbors only

Time: O(n log n) - sorting cost
Space: O(1) or O(n) depending on sort algorithm

Approach 3: HashSet (Optimal)
[1, 2, 3, 1]

Check 1: Not in set → Add {1}
Check 2: Not in set → Add {1, 2}
Check 3: Not in set → Add {1, 2, 3}
Check 1: Already in set! → Return true

Time: O(n) - single pass
Space: O(n) - store seen elements

---

🎯 Approach 1: Brute Force (Compare All Pairs)

The Most Natural Thinking 💭

Core Logic:

Compare every element with every other element:
- For each element at index i
  - Compare with all elements at index j > i
  - If nums[i] == nums[j] → found duplicate

Why This Works: - Checks all possible pairs exhaustively - Guaranteed to find duplicate if it exists - No additional data structures needed

Why This is Slow: - Nested loops → O(n²) complexity - For 10,000 elements → 50 million comparisons - Times out on large inputs

Implementation

public boolean containsDuplicate(int[] nums) {
    // Check every pair of elements
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] == nums[j]) {
                return true;  // Found duplicate
            }
        }
    }
    return false;  // No duplicates found
}

Step-by-Step Execution: nums = [1,2,3,1]

i=0, nums[0]=1:
├─ Compare with j=1, nums[1]=2: 1≠2 ✗
├─ Compare with j=2, nums[2]=3: 1≠3 ✗
└─ Compare with j=3, nums[3]=1: 1=1 ✓ DUPLICATE!
   Return true

Total comparisons: 3

⏰ Time: O(n²)
💾 Space: O(1)

---

🎯 Approach 2: Sorting

Thought Process 💭

Core Logic:

Key Insight: After sorting, duplicates become adjacent!

Steps:
1. Sort the array
2. Check adjacent elements
3. If any two neighbors are equal → duplicate exists

Why This Works: - Sorting groups identical elements together - Only need to check neighbors (not all pairs) - Reduces comparisons from n² to n

Trade-off: - Sorting costs O(n log n) time - Faster than brute force but slower than hash set - May modify original array

Implementation

public boolean containsDuplicate(int[] nums) {
    // Sort array in ascending order
    Arrays.sort(nums);

    // Check adjacent elements
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;  // Found adjacent duplicates
        }
    }

    return false;  // No duplicates found
}

Step-by-Step Execution: nums = [1,3,2,1]

Initial: [1, 3, 2, 1]

After sorting: [1, 1, 2, 3]
                ↓  ↓
                Adjacent!

Check i=0: nums[0]=1, nums[1]=1 → 1=1 ✓ DUPLICATE!
Return true

Total operations: Sort + 1 comparison

⏰ Time: O(n log n) - dominated by sorting
💾 Space: O(1) if in-place sort, O(n) for some sort algorithms

---

✅ Approach 3: HashSet (Optimal)

The Breakthrough Insight 💡

Core Logic:

Key Observation:
We don't need to know WHERE duplicates are
We only need to know IF we've SEEN this element before

Solution:
Use HashSet to remember seen elements:
- For each element:
  - If already in set → duplicate found!
  - If not in set → add to set, continue

Why This is Better: - O(1) lookup time in hash set - Single pass through array - Early termination when duplicate found - Most intuitive approach

Trade-off: - Uses O(n) extra space for hash set - Space-time tradeoff (faster but uses memory)

Implementation

public boolean containsDuplicate(int[] nums) {
    HashSet<Integer> seen = new HashSet<>();

    for (int num : nums) {
        // Check if we've seen this number before
        if (seen.contains(num)) {
            return true;  // Duplicate found!
        }
        // Add to set for future checks
        seen.add(num);
    }

    return false;  // No duplicates
}

Step-by-Step Execution: nums = [1,2,3,1]

Initial: seen = {}

Check num=1:
├─ Is 1 in seen? No
├─ Add 1 to seen
└─ seen = {1}

Check num=2:
├─ Is 2 in seen? No
├─ Add 2 to seen
└─ seen = {1, 2}

Check num=3:
├─ Is 3 in seen? No
├─ Add 3 to seen
└─ seen = {1, 2, 3}

Check num=1:
├─ Is 1 in seen? YES! ✓
└─ Return true immediately

═══════════════════════════════════════════════
🎯 RESULT: true (found duplicate)
═══════════════════════════════════════════════
Checked 4 elements, found duplicate at element 4

Another Example: nums = [1,2,3,4]

Check num=1: Not in seen → Add → seen={1}
Check num=2: Not in seen → Add → seen={1,2}
Check num=3: Not in seen → Add → seen={1,2,3}
Check num=4: Not in seen → Add → seen={1,2,3,4}

Reached end of array → No duplicates
Return false

⏰ Time: O(n) - single pass
💾 Space: O(n) - hash set storage

---

🔍 Edge Cases

Case 1: All duplicates
Input: [1,1,1,1]
Output: true
Strategy: Found at second element

Case 2: No duplicates
Input: [1,2,3,4,5]
Output: false
Strategy: Must check entire array

Case 3: Two elements, duplicate
Input: [1,1]
Output: true
Strategy: Minimum duplicate case

Case 4: Two elements, no duplicate
Input: [1,2]
Output: false

Case 5: Duplicate at end
Input: [1,2,3,4,4]
Output: true
Strategy: Must check entire array

Case 6: Single element
Input: [1]
Output: false
Reason: Need at least 2 elements for duplicate

Case 7: Large numbers
Input: [1000000000, 1000000000]
Output: true
Strategy: Hash set handles large numbers

Case 8: Negative numbers
Input: [-1, -2, -3, -1]
Output: true
Strategy: Works with negatives too

---

Common Mistakes

Mistake 1: Not checking empty array
❌ Wrong: Assume array has elements
✓ Right: Handle n=0 or n=1 (though constraints say n≥1)

Mistake 2: Modifying original array without permission
❌ Wrong: Sort array in-place when not allowed
✓ Right: Ask if modification allowed or use hash set

Mistake 3: Forgetting hash set contains() check
❌ Wrong: seen.add(num) without checking first
✓ Right: Check contains() BEFORE adding

Mistake 4: Using HashMap instead of HashSet
❌ Wrong: Map<Integer, Integer> (unnecessary value)
✓ Right: HashSet<Integer> (only need keys)

Mistake 5: Not returning early
❌ Wrong: Continue after finding duplicate
✓ Right: Return true immediately when found

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²) - nested loops
  Space: O(1)
  Use: Never (too slow)

Approach 2: Sorting  
  Time: O(n log n) - sort dominates
  Space: O(1) or O(n)
  Use: When space is limited

Approach 3: HashSet (BEST)
  Time: O(n) - single pass
  Space: O(n) - store elements
  Use: Default choice (fastest)

🔑 The Core Insight

Problem asks: "Have we seen this before?"

This is a membership test problem:
→ Perfect use case for hash set
→ O(1) lookup for "is element in set?"
→ Trade space for time

Pattern Recognition:
"Contains duplicate" = "Seen before" = Hash Set

🎯 Pattern Recognition

Problem Type: Duplicate Detection
Core Pattern: Tracking seen elements

When to Apply:
✓ Need to detect duplicates in array
✓ "Have we seen X before?" questions
✓ Can use extra space for speed
✓ Order doesn't matter

Key Data Structure:
→ HashSet for O(1) membership testing

Related Problems:
- Contains Duplicate II (LC 219)
- Contains Duplicate III (LC 220)
- Single Number (LC 136)
- Find All Duplicates in Array (LC 442)

🧠 Interview Strategy

Step 1: "Need to detect if any element appears twice"
Step 2: "Brute force is O(n²) comparing all pairs"
Step 3: "Sorting brings duplicates together - O(n log n)"
Step 4: "HashSet gives O(1) lookup - optimal at O(n)"
Step 5: "Trade O(n) space for O(n) time - worth it!"

---

📝 Quick Revision Notes

🎯 Core Concept:

Use HashSet to track seen elements. Check if element exists before adding. If exists → duplicate found!

⚡ Quick Implementation:

public boolean containsDuplicate(int[] nums) {
    HashSet<Integer> seen = new HashSet<>();

    for (int num : nums) {
        if (seen.contains(num)) return true;
        seen.add(num);
    }

    return false;
}

🔑 Key Insights:

• HashSet is perfect for "seen before" checks
• O(1) lookup makes it fast
• Check before adding to detect duplicates
• Early return when duplicate found
• Space-time tradeoff worth it (O(n) space for O(n) time)

🎪 Memory Aid:

"Seen it before? Yes → duplicate! No → remember it!"
Think: "HashSet = membership test = O(1) magic"

---

Related Patterns

• Contains Duplicate II (LC 219) - duplicates within distance k
• Single Number (LC 136) - find unique element
• Find All Duplicates in Array (LC 442)

---

Happy practicing! 🎯