The O(n) Club: How to Handle Array Doppelgängers Without Losing Your Sanity

The O(n) Club: How to Handle Array Doppelgängers Without Losing Your Sanity

⚡ TL;DR

This is that magical Leetcode problem where duplicates finally get the attention they crave: find all elements (with duplicates!) that occur in both arrays—the number of times they overlap, no more, no less. Brute force will get you late-night regrets, so do yourself a favor and use a hash map:

// Please don't do this in an interview:
List
<integer> result = new ArrayList<>();
boolean[] visited = new boolean[nums2.length];
for (int i = 0; i < nums1.length; i++) {
  for (int j = 0; j < nums2.length; j++) {
    if (!visited[j] && nums1[i] == nums2[j]) {
      result.add(nums1[i]);
      visited[j] = true;
      break;
    }
  }
}</integer>

🧠 How Devs Usually Mess This Up

If you gleefully grab only unique numbers for your intersection—congrats, you miss most real interviews. Lots of devs forget: duplicates really, truly matter. Others play Simon Says about order, when the problem couldn’t care less. Some poor souls don’t stop at the minimum overlap per element, so their output is the AI’s fever dream, not the interviewer’s spec. Don’t be that dev.

🔍 What’s Actually Going On

Imagine two robot chefs prepping the same ingredient list. If Chef One has mushrooms four times and Chef Two bought them only twice, the shared grocery haul is just two mushrooms—period. No chef gets a fantasy shipment. The intersection is simply the number of times both arrays share an item, so each doppelgänger only gets a ticket to the party if both lists agree. Want it visual? It’s Venn diagram meets corporate bureaucracy: only what’s stamped on both forms makes it in. Twice if that’s the overlap, but not a single time more.

🛠️ PseudoCode

• Step 1: Toss everything from one array into a HashMap as counts.
  Map<Integer, Integer> count = new HashMap<>(); for (int num : nums1) count.put(num, count.getOrDefault(num, 0) + 1);
• Step 2: Walk through the second array. If the map still says you have one, add to result and decrease the counter. No more freebies than the minimum in either bag.
  for (int num : nums2) { if (count.getOrDefault(num, 0) > 0) { result.add(num); count.put(num, count.get(num) - 1); } }
• Step 3: Return the result as int[]. Interviewers are oddly attached to Java types.

💻 The Code

public int[] intersect(int[] nums1, int[] nums2) {
    Map<integer integer> count = new HashMap<>();
    for (int num : nums1) {
        count.put(num, count.getOrDefault(num, 0) + 1);
    }
    List
<integer> result = new ArrayList<>();
    for (int num : nums2) {
        if (count.getOrDefault(num, 0) > 0) {
            result.add(num);
            count.put(num, count.get(num) - 1);
        }
    }
    int[] out = new int[result.size()];
    for (int i = 0; i < result.size(); i++) out[i] = result.get(i);
    return out;
}</integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Only include an element as many times as it appears in both arrays—not whichever has more. No extra mushroom risotto.
• No need to sort. Seriously, save yourself the cycles—hash map’s got you covered. (Two pointers on sorted arrays only makes sense if you’re low on memory or hate hash maps.)
• If either array is empty, your intersection will also be a beautiful, empty array. Don’t panic.
• Time: O(m + n) for hash maps. Sorting would add O(m log m + n log n); only go there if someone with a suit demands it.
• Result order? It’s the wild west out there. No one cares. Do not lose sleep over it.

🧠 Interviewer Brain-Tattoo

“Duplicates are like receipts: you only match as many as you kept. Anything else is just wishful accounting.”