The O(n) Club: Contains Duplicate: The HashSet Supremacy Edition

The O(n) Club: Contains Duplicate—The HashSet Supremacy Edition

⚡ TL;DR

Want to bully an array into confessing its duplicates? Toss everything into a HashSet. When you catch a repeat, congratulate yourself (with true) and clock out early.

// Fast & simple Java
public boolean containsDuplicate(int[] nums) {
    Set
<integer> seen = new HashSet<>();
    for (int num : nums) {
        if (!seen.add(num)) return true;
    }
    return false;
}
</integer>

🧠 How Devs Usually Mess This Up

Classic rookie movie: You write two nested loops and try every number against every other one, savoring O(n²) slowness and hoping brute force will impress your interviewer. Or you get fancy with array sorting—because, why not add O(n log n) when you could use O(n)? Pro tip: This isn’t “Who Wants To Be a Millionaire.” You’re not paid by the operation.

Oh, and some forget it’s just a yes/no situation. No need to list or count the culprits. It’s a boolean, Chandler. True if you spot a duplicate. False otherwise. The end.

🔍 What’s Actually Going On

This is the bouncer-at-the-nightclub algorithm. The HashSet sits at the velvet rope, checking IDs. Anyone who’s already on the list tries to get in again? Caught. Club doors slam. You don’t care who—they’re just not getting another drink. And you do not need a guestbook, a roster, or any baroque tracking system. Just the set. If you walk the array once without issues, everyone’s unique and the party’s safe.

🛠️ PseudoCode

• Initialize a HashSet — This is your guestlist enforcer.
• For each number in the array:
  • If the number is already in the set
  •   > Return true immediately (busted!)
  • Otherwise, add number to the set
• Return false — If you check everyone and the bouncer shrugs, there are no twins.

// Java-flavored pseudocode
Set seen = new HashSet();
for (num in nums) {
  if (seen.contains(num)) return true;
  seen.add(num);
}
return false;

💻 The Code

import java.util.HashSet;
import java.util.Set;
 public class ContainsDuplicate {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                return true;
            }
        }
        return false;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty array? Returns false. (Nothing to duplicate, nothing to see.)
• Single element? Still false. (Try again with siblings.)
• All unique? Returns false. You got lucky—this never happens in real data.
• Do NOT mutate or sort the input: The interviewer can see right through you, and they don’t like it when you shuffle their data.
• O(n) time with O(n) space, worst-case if all values are unique. HashSet’s memory bill may not be free, but hey, neither are your billable hours.
• Never brute-force! Real interviews have timeouts. Your patience does not.

🧠 Interviewer Brain-Tattoo

Repeat after me: “When duplicate detection is the gig, HashSet is the rig.” (Bonus points if you say it out loud in Chandler’s voice.) And if you write nested loops by choice, the LeetCode fairies lose their wings.