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 < nnums1[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.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228Problem 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.
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.
Time Complexity: O(n^2), with each pair calculation taking constant time.
Space Complexity: O(n^2), using space for hash map storage.
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.
| Approach | Complexity |
|---|---|
| Using Hash Maps to Store Sums | Time Complexity: O(n^2), with each pair calculation taking constant time. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Four Nested Loops | O(n^4) | O(1) | Small input sizes or when explaining the baseline logic before optimization |
| Hash Map Pair Sums | O(n^2) | O(n^2) | General case and interview solution; efficient counting using hash map lookups |
Quadruplet Sum II HashMap and Heap | Leetcode 454. 4sum ii Solution • Pepcoding • 7,220 views views
Watch 9 more video solutions →Practice 4Sum II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor