← Two PointersDSA 1.1.G

Hash + Enumerate

Split into halves, hash one, enumerate the other. 4Sum II.

StatusCollected
Notes1 solved

Not really "two pointers" in the walking sense — this one earns its place in the pattern by splitting the problem into two halves the same way the k-Sum family does, just swapping the second pointer scan for a hash lookup.

int fourSumCount(int *A, int *B, int *C, int *D, int n) {
      /* hash every possible A[i]+B[j] sum -> how many times it occurs */
      HashMap sums = {0};
      for (int i = 0; i < n; i++)
          for (int j = 0; j < n; j++)
              sums[A[i] + B[j]]++;

      int count = 0;
      for (int k = 0; k < n; k++)
          for (int l = 0; l < n; l++)
              count += sums[-(C[k] + D[l])];   /* look up the negation */

      return count;
  }

Four nested loops would be O(n⁴). Hashing every A[i]+B[j] sum first turns the second half into O(n²) lookups instead of another O(n²) nested scan against the first half — the same halving instinct as k-Sum, just resolved with a hash map instead of a sorted array and pointers.

Notes from readers

Comments — via GitHub