031 — Contains Duplicate

31 — Contains Duplicate

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

---

🍽️ Intuition

Imagine you're a bouncer at a club with a guest list, and your only job tonight is to catch anyone who tries to walk in twice. The dumbest way to do it: every time someone new arrives, turn around and re-scan the entire line of people already inside, name by name, hoping you spot a match. Exhausting, and it gets slower the more people arrive.

The smart bouncer keeps a notepad. Every time someone walks in, they check the notepad — instantly, because it's alphabetized in their head — and if the name's already there, they stop them at the door. Otherwise, they jot the name down and wave them through. One pass through the line, one glance at the notepad per person.

---

🚩 Pattern-Recognition Cue

Any phrasing that boils down to "has this exact value shown up before?" — "contains duplicate," "return true if any element repeats," "find if there's a repeated value" — is a membership-check problem in disguise. Whenever the question is about seen-before rather than position or order, a hash set is almost always the fastest tool available, because a set answers "have I seen this?" in O(1).

---

🐢 Brute Force

Compare every pair of elements. If any two (at different indices) are equal, we've found a duplicate.

func containsDuplicateBruteForce(_ nums: [Int]) -> Bool {
    for i in 0..<nums.count {
        for j in (i + 1)..<nums.count {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

Big-O: O(n²) time — a nested loop checking every pair. O(1) extra space.

---

🚀 Optimal

Walk the array once, keeping a hash set of everything seen so far. If we ever try to insert a value that's already in the set, we've found our duplicate immediately.

func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()
    for num in nums {
        if !seen.insert(num).inserted {
            return true   // insert() reports it was already present
        }
    }
    return false
}

Big-O: O(n) time — one pass, O(1) average per hash-set operation. O(n) space for the set in the worst case (no duplicates, so everything gets stored).

---

🔑 The Key Insight

The brute force re-derives "have I seen this value?" from scratch for every element by re-scanning everything before it — that repeated scanning is exactly what a hash set eliminates. A Set turns "have I seen this?" from an O(n) scan into an O(1) average lookup, so trading O(n) space for a set collapses the total work from O(n²) down to O(n). This is the most direct example of the classic time-for-space trade-off: remembering what you've seen is cheaper than re-checking everything you've seen.

---

🔗 Related Chapters

• Hash Maps & Hash Sets — the Set insert/membership mechanics this solution leans on directly.
• Arrays & Strings — the input structure being scanned.
• Big-O Notation — for the O(n²) → O(n) trade-off reasoning above.
• Two Pointers — disclosed as a loose fit, not a natural one: the actual optimal solution above replaces pairwise comparison with hashing, not a two-pointer scan, so there's no genuine two-pointer code here. The only thread connecting it to this chapter is the brute force's nested i/j loop in containsDuplicateBruteForce, comparing every pair — that O(n²) pairwise-comparison starting point is exactly the shape Two-Pointers techniques exist to collapse into a single coordinated pass, even though this problem collapses it with a hash set instead.

---

🧸 Memory Sentence

Contains Duplicate is a bouncer with a notepad — one glance at who's already inside beats re-scanning the whole line for every new arrival.

---

✅ Check Your Understanding

The optimal solution uses Set<Int>. Suppose instead you were asked "return true if any value appears more than twice" — would a Set alone still be enough, or would you need a different data structure? Explain what changes and why.

---

⬅️ Previous: Bit Manipulation Tricks · Next: Valid Anagram ➡️