4Sum II

Problem

Given four integer arrays a, b, c, d of equal length n, count the number of index tuples (i, j, k, l) such that a[i] + b[j] + c[k] + d[l] == 0. The trick is to fold the 4-way O(n⁴) search into two O(n²) passes with a hash map of pair sums.

Constraints

• n == a.length == b.length == c.length == d.length
• 1 ≤ n ≤ 200
• −2²⁸ ≤ values ≤ 2²⁸

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def fourSumCount(self, a, b, c, d):
        from collections import Counter
        ab = Counter(x + y for x in a for y in b)
        return sum(ab[-(x + y)] for x in c for y in d)

Java

class Solution {
    public int fourSumCount(int[] a, int[] b, int[] c, int[] d) {
        Map<Integer, Integer> ab = new HashMap<>();
        for (int x : a) {
            for (int y : b) {
                ab.merge(x + y, 1, Integer::sum);
            }
        }
        int res = 0;
        for (int x : c) {
            for (int y : d) {
                res += ab.getOrDefault(-(x + y), 0);
            }
        }
        return res;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.