Four Sum Count

Published at16 Mar 2026

Like0

You are given four integer arrays A, B, C, and D. The goal is to count how many tuples (i, j, k, l) satisfy:

A[i] + B[j] + C[k] + D[l] = 0

This is a counting problem, not a search-for-one-answer problem. If many different index combinations add up to zero, all of them should be included in the final count.

For example, if A=[1,2], B=[-2,-1], C=[-1,2], and D=[0,2], the answer is 2. If all four arrays are just [0], the answer is 1 because there is exactly one tuple and its sum is zero.

So the task is to count every valid four-array combination whose total sum is zero.

Example Input & Output

Example 1

Input

A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]

Output

Explanation

Two tuples satisfy sum zero.

Example 2

Input

A=[0], B=[0], C=[0], D=[0]

Output

Explanation

Only one tuple and it sums to zero.

Example 3

Input

A=[1], B=[1], C=[1], D=[1]

Output

Explanation

No tuple sums to zero.

Algorithm Flow

Recommendation Algorithm Flow for Four Sum Count

Solution Approach

A direct brute-force solution would check every combination from the four arrays, but that takes O(n^4) time, which gets expensive very quickly. The hash table trick is to split the equation into two halves.

Instead of trying all four arrays at once, first compute every possible sum of one value from A and one value from B. Store those sums in a map where the key is the sum and the value is how many times that sum appears.

For example, if the sum 1 can be made in three different ways from A and B, the map should store 1 -> 3.

Then iterate through every pair from C and D. Suppose their sum is cd. To make the total zero, we need a matching sum of -cd from the first half. If the map contains that key, add its stored count to the answer.

This works because each stored A + B pair can combine with each matching C + D pair to form a valid tuple. The final complexity becomes O(n^2) time and O(n^2) space, which is the standard efficient approach for this problem.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int four_sum_count(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> ab = new HashMap<>();
        for (int a : A) {
            for (int b : B) {
                int s = a + b;
                ab.put(s, ab.getOrDefault(s, 0) + 1);
            }
        }
        int ans = 0;
        for (int c : C) {
            for (int d : D) {
                ans += ab.getOrDefault(-(c + d), 0);
            }
        }
        return ans;
    }
}

javascript

function four_sum_count(A, B, C, D) {
    const ab = {};
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B.length; j++) {
            const s = A[i] + B[j];
            ab[s] = (ab[s] || 0) + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < C.length; i++) {
        for (let j = 0; j < D.length; j++) {
            ans += (ab[-(C[i] + D[j])] || 0);
        }
    }
    return ans;
}

php

<?php
function four_sum_count($A, $B, $C, $D) {
    $ab = [];
    foreach ($A as $a) {
        foreach ($B as $b) {
            $k = (string)($a + $b);
            $ab[$k] = ($ab[$k] ?? 0) + 1;
        }
    }
    $ans = 0;
    foreach ($C as $c) {
        foreach ($D as $d) {
            $need = (string)(-($c + $d));
            $ans += ($ab[$need] ?? 0);
        }
    }
    return $ans;
}
?>

python

from typing import List

def four_sum_count(A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    ab = {}
    for a in A:
        for b in B:
            s = a + b
            ab[s] = ab.get(s, 0) + 1
    ans = 0
    for c in C:
        for d in D:
            ans += ab.get(-(c + d), 0)
    return ans

rust

use std::collections::HashMap;
fn four_sum_count(A: Vec<i32>, B: Vec<i32>, C: Vec<i32>, D: Vec<i32>) -> i32 {
    let mut ab: HashMap<i32, i32> = HashMap::new();
    for a in A.iter() {
        for b in B.iter() {
            *ab.entry(*a + *b).or_insert(0) += 1;
        }
    }
    let mut ans = 0;
    for c in C.iter() {
        for d in D.iter() {
            ans += *ab.get(&(-(*c + *d))).unwrap_or(&0);
        }
    }
    ans
}

typescript

function four_sum_count(A: number[], B: number[], C: number[], D: number[]): number {
    var ab: { [key: string]: number } = {};
    for (var i = 0; i < A.length; i++) {
        for (var j = 0; j < B.length; j++) {
            var s = String(A[i] + B[j]);
            ab[s] = (ab[s] || 0) + 1;
        }
    }
    var ans = 0;
    for (var x = 0; x < C.length; x++) {
        for (var y = 0; y < D.length; y++) {
            var need = String(-(C[x] + D[y]));
            ans += (ab[need] || 0);
        }
    }
    return ans;
}

Related Hash Table Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Four Sum Count

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Hash Table Challenges

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.