The O(n) Club: Intersection of Two Arrays: When HashSets Save Your Sanity (and Your CPU)

The O(n) Club: Intersection of Two Arrays — When HashSets Save Your Sanity (and Your CPU)

⚡ TL;DR

You want all unique elements from both arrays. No repeats. Output order? Who cares. Here’s the brute force Java anti-pattern most of us regret trying once:

// Brute force: Not for the faint of RAM
Set<Integer> result = new HashSet<>();
for (int num1 : nums1) {
    for (int num2 : nums2) {
        if (num1 == num2) result.add(num1);
    }
}
// Clunky. Slow. But technically works.

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Imagine two mailing lists for a developer conference afterparty: you want to send swag only to attendees who showed up on both lists. You don’t invite someone twice if they show up with a mustache and sunglasses. Also, nobody checks the RSVP order. You make a HashSet from one list (because it’s fast and forgets duplicates like yesterday’s bad code). Then you blitz through the second list, plucking names already in the set. Pizza, party, perfection.

🛠️ PseudoCode

• Step 1: Dump all items from nums1 into a HashSet.
  

  Set<Integer> firstSet = new HashSet<>();
  for (int x : nums1) firstSet.add(x);

• Step 2: Loop through nums2. If something’s in firstSet, add it to the result set.
  

  Set<Integer> result = new HashSet<>();
  for (int y : nums2) if (firstSet.contains(y)) result.add(y);

• Step 3: Dump the result set into an int[] array.
  

  int[] output = result.stream().mapToInt(Integer::intValue).toArray();

• Why not cram all this in one loop? Because it’s easier to keep your logic—and your sanity—separate. HashSet guards against both bugs and boredom.

💻 The Code

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> firstSet = new HashSet<>();
    for (int x : nums1) firstSet.add(x);
    Set<Integer> result = new HashSet<>();
    for (int y : nums2)
        if (firstSet.contains(y)) result.add(y);
    int[] output = new int[result.size()];
    int i = 0;
    for (int num : result) output[i++] = num;
    return output;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• No duplicates allowed! If your output is [3,3], congrats, you mixed up the question or your HashSet went on strike.
• Order is irrelevant. Sorting won’t win you friends or points—unless you absolutely love burning CPU cycles.
• Big numbers. If you’re working with huge arrays, mind the memory. But for most humans, HashSet is cheap therapy.
• Nested loops. Avoid unless you’re mining bitcoin with your laptop as a side hustle.
• Complexity: O(n + m) time (n = nums1, m = nums2), and O(unique elements) in space.

🧠 Interviewer Brain-Tattoo

“Intersection without duplicates: If you’re fumbling with order or sorting, you’re officially debugging the wrong bug.”