Four Sum Count

Like0

In Four Sum Count, you’re given four integer arrays (A, B, C, D). Your task is to return the total number of tuples (i,j,k,l) such that their sum equals zero. This challenge tests your ability to handle complex combinations with maximum efficiency!

The "secret sauce" here is a clever Hash Map to avoid a slow brute-force approach. Instead of checking every combination (which would be O(N⁴)), you split the problem in half. First, calculate all possible sums of pairs from A and B and store them in a map with their frequency. Then, calculate sums from C and D and ask your map: "Do I have a previous sum that, when added to this one, equals zero?" This turns a massive problem into a lightning-fast O(N²) solution! It’s a brilliant leap in thinking that teaches you how to "divide and conquer" complexity using memory strategically. Even millions of combinations become easy to handle!

Keep the algorithm focused on one clear invariant and update path so correctness is easy to verify from left to right. This reduces accidental branching errors and helps ensure the final output stays consistent with the problem contract across random and adversarial test shapes.

Examples

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 - Budibadu

Best Answers

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;
}

Comments (0)

Join the Discussion

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

Four Sum Count

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Hash Table Problems

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Ransom Note

Two Sum Indices

Comments (0)

Join the Discussion