Skip to main content
Talentd

4Sum II - Solution & Explanation

MediumArrayHash Table13 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

 

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

 

Constraints:

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

Approach Overview

Problem Overview: 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. A naive approach checks every possible combination, but the real challenge is reducing the exponential search using a smarter lookup strategy.

Approach 1: Brute Force with Four Nested Loops (O(n4) time, O(1) space)

The most direct method iterates through every element of all four arrays using four nested loops. For each combination (i, j, k, l), compute the sum and increment the result when it equals zero. This approach demonstrates the full search space and confirms correctness, but it quickly becomes impractical as n grows. With arrays of size 200, the algorithm may check billions of combinations. This version mainly serves as a conceptual baseline before optimizing with better data structures.

Approach 2: Hash Map Pair Sums (O(n2) time, O(n2) space)

The optimal solution reduces the four-sum problem into two independent two-sum problems. First iterate through arrays A and B and compute every possible pair sum a + b. Store these sums in a hash map where the key is the sum and the value is the number of times that sum appears. This preprocessing step takes O(n2) time.

Next iterate through arrays C and D. For each pair compute c + d, then check if -(c + d) exists in the hash map. A constant-time hash lookup immediately tells you how many matching pairs from A and B can complete the equation. Add that frequency to the answer. This effectively counts all tuples whose sums cancel out to zero.

The key insight: instead of evaluating four numbers at once, precompute half of the equation and reuse it with fast lookups. The hash table stores pair frequencies, while the arrays are scanned with simple nested loops. This reduces the search space from n⁴ combinations to roughly 2 * n² operations. The idea is common in multi-sum problems and builds directly on patterns from array pair-sum techniques.

Recommended for interviews: Interviewers expect the hash map pair-sum solution. Starting with the brute force approach shows you understand the problem space, but optimizing to O(n²) using a frequency map demonstrates algorithmic insight and familiarity with hash-based counting patterns. This approach balances performance and clarity, and it is the standard solution used in most production implementations.

Approach 1: Using Hash Maps to Store Sums

This approach leverages hash maps to efficiently count and use pair sums. First, we compute all possible sums between arrays nums1 and nums2, storing them in a hash map along with their count. Then, we iterate over pairs of nums3 and nums4, checking how many complements (to form a sum of zero) exist in the hash map.

The given C solution defines a hash map structure using the UT hash library. It stores sums of pairs from nums1 and nums2 in a hash map. For each pair in nums3 and nums4, it checks how many complementary sums exist in the hash map, contributing to the tuple count.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), with each pair calculation taking constant time.
Space Complexity: O(n^2), using space for hash map storage.

Try this approach in the editor →

Approach 2: Hash Table

We can add the elements a and b in arrays nums1 and nums2 respectively, and store all possible sums in a hash table cnt, where the key is the sum of the two numbers, and the value is the count of the sum.

Then we iterate through the elements c and d in arrays nums3 and nums4, let c+d be the target value, then the answer is the cumulative sum of cnt[-(c+d)].

The time complexity is O(n^2), and the space complexity is O(n^2), where n is the length of the array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Hash Maps to Store Sums

Time Complexity: O(n^2), with each pair calculation taking constant time.
Space Complexity: O(n^2), using space for hash map storage.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Four Nested LoopsO(n^4)O(1)Small input sizes or when explaining the baseline logic before optimization
Hash Map Pair SumsO(n^2)O(n^2)General case and interview solution; efficient counting using hash map lookups

Video Solution

Quadruplet Sum II HashMap and Heap | Leetcode 454. 4sum ii Solution • Pepcoding • 7,247 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is 4Sum II easy or hard?
4Sum II is rated Medium difficulty. The brute force idea is straightforward, but recognizing the pair-sum hash map optimization requires familiarity with hash-based counting patterns.
4Sum II Python/Java solution
Python and Java implementations follow the same strategy: compute pair sums of the first two arrays using a dictionary or HashMap, then iterate through the other two arrays and accumulate matches using complement lookups.
How to solve 4Sum II in O(n^2)?
Precompute all pair sums from arrays A and B and store them in a hash map with their frequencies. Then iterate over pairs from C and D and check if the complement -(c + d) exists in the map. Each lookup counts how many valid tuples complete the zero sum.
What is the best approach for 4Sum II?
The hash map pair-sum approach is the most efficient. Compute all sums of A[i] + B[j] and store their frequencies in a hash map. Then iterate through pairs from C and D and look up the complement -(c + d). This reduces the complexity from O(n^4) to O(n^2).
Is 4Sum II asked at Google/Amazon/Meta?
Variants of multi-sum and pair-sum counting problems appear in interviews at companies like Amazon, Google, and Meta. The problem tests hash map usage, frequency counting, and the ability to reduce a higher-dimensional search space.
What data structure is used in 4Sum II?
A hash map (hash table) is the primary data structure. It stores frequencies of pair sums so the algorithm can perform constant-time lookups while scanning the remaining arrays.
What is the time complexity of 4Sum II?
The optimal solution runs in O(n^2) time. It builds a hash map of pair sums from the first two arrays in O(n^2), then scans pair sums from the remaining arrays with constant-time hash lookups.

Ready to solve this problem?

Practice 4Sum II with our built-in code editor and test cases.

Practice on FleetCode
Previous

4Sum