The O(n) Club: 4Sum II — When Hashmaps Save You from Loop Purgatory

The O(n) Club: 4Sum II — When Hashmaps Save You from Loop Purgatory

⚡ TL;DR

Given four integer arrays, count (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0. Brute-force = four loops and eternal suffering. Hashmap = two loops and enough free time to make a fresh coffee.

// Don't. Just... don't.
int count = 0;
for (int a : nums1)
  for (int b : nums2)
    for (int c : nums3)
      for (int d : nums4)
        if (a + b + c + d == 0)
          count++;
// Runtime: Somewhere between "never" and "heat death of universe"

🧠 How Devs Usually Mess This Up

Ah, the four-array panic: your first instinct is to nest four for-loops, right? Congratulations, you’ve just invented the world’s slowest lottery machine! Others think this is “4Sum Classic” and scramble to deduplicate quadruplets or sort arrays—totally unnecessary. 4Sum II just wants the raw count, not a curated playlist of unique sums.

🔍 What’s Actually Going On

This problem is secretly about teamwork: split the arrays in half, pairwise add the first two, and stash all their sums in a HashMap (with count of occurrences). Now, for every sum from the other two arrays, just look up its negative in your map—because (a + b + c + d) == 0 exactly when a + b == -(c + d). It’s like coding with a calculator, but faster and with 99% less cursing.

🛠️ PseudoCode

• Hash all possible a + b sums:

  Map<Integer, Integer> abMap = new HashMap<>();
  for (int a : nums1)
    for (int b : nums2)
      abMap.put(a + b, abMap.getOrDefault(a + b, 0) + 1);

  Now abMap holds “sum” → frequency, like a bouncer tracking repeat guests.

• For each c + d, check: how many (a, b) pairings cancel them out?

  int count = 0;
  for (int c : nums3)
    for (int d : nums4)
      count += abMap.getOrDefault(-(c + d), 0);

  If the complement exists, add up its frequency. If not, add zero. It’s basically algorithmic matchmaking.

• Return the count. No sorting, no deduplication, just joy.

  return count;

💻 The Code

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    Map<Integer, Integer> abMap = new HashMap<>();
    for (int a : nums1)
        for (int b : nums2)
            abMap.put(a + b, abMap.getOrDefault(a + b, 0) + 1);
    int count = 0;
    for (int c : nums3)
        for (int d : nums4)
            count += abMap.getOrDefault(-(c + d), 0);
    return count;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Looking up (c + d) instead of its negative: You’ll wonder why you always get zero, and probably lose sleep.
• Trying to deduplicate quadruplets: Yawn. Just count the matches, and live your best life.
• HashMap memory binge: HashMap will take up to O(n²) space, so if your arrays are as long as the daily Jira backlog, watch the RAM.
• Time & Space, No Gym Required: O(n²) in both; manageable for typical input sizes, infinitely better than O(n⁴) loops-of-doom.

🧠 Interviewer Brain-Tattoo

Brute-forcers blame slow CPUs. Hashmappers blame nothing — their code runs before the pizza arrives.