What pattern does 4Sum II use?

The Pattern: Hash Maps (Complement Counting) The Heuristic: When counting tuples across multiple arrays that sum to a target, precompute sums of pairs from half the arrays and store frequencies in a hash map, then check complements from the other half to reduce complexity from exponential to quadratic.

4Sum II - LeetCode Solution & Explanation

Q: What is the time complexity of 4Sum II?

O(n^2). The algorithm computes all pair sums from nums1 and nums2 in O(n^2), and similarly iterates over all pair sums from nums3 and nums4 in O(n^2). Each hash map lookup is O(1) on average, resulting in O(n^2) total time.

Problem

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

n == nums1.length == nums2.length == nums3.length == nums4.length
1 ≤ n ≤ 200
−2²⁸ ≤ nums1[i], nums2[i], nums3[i], nums4[i] ≤ 2²⁸

Example

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

Output: 2

The two tuples are: - (0, 0, 0, 1): 1 + (-2) + (-1) + 2 = 0 - (1, 1, 0, 0): 2 + (-1) + (-1) + 0 = 0 A brute-force approach would check all quadruples, which is O(n^4). Instead, the algorithm precomputes sums of pairs from nums1 and nums2, storing their frequencies in a hash map. Then it iterates over pairs from nums3 and nums4, checking if the negated sum exists in the map. This reduces the problem to two nested loops and a hash map lookup, achieving O(n^2) time.

Approach

Straightforward Solution

A brute-force approach enumerates all quadruples (i, j, k, l) and checks if their sum is zero, resulting in O(n^4) time complexity, which is infeasible for n up to 200.

Core Observation

The problem requires counting quadruples where the sum of four elements equals zero. This can be reframed as finding pairs of sums from two arrays that complement pairs of sums from the other two arrays to zero.

Path to Optimal

By splitting the problem into two halves, the sums of pairs from nums1 and nums2 can be precomputed and stored in a hash map with their frequencies. Then, for each pair sum from nums3 and nums4, the algorithm checks if the negated sum exists in the map. This reduces the complexity to O(n^2) for both halves, resulting in an overall O(n^2) time complexity.

Optimal Approach

Compute all possible sums of pairs from nums1 and nums2, storing the count of each sum in a hash map. Then iterate over all sums of pairs from nums3 and nums4, and for each sum, check if its negation exists in the hash map. Accumulate the counts accordingly. This approach leverages the hash map for constant-time lookups, efficiently counting all quadruples summing to zero.

Time

O(n^2)

The algorithm computes all pair sums from nums1 and nums2 in O(n^2), and similarly iterates over all pair sums from nums3 and nums4 in O(n^2). Each hash map lookup is O(1) on average, resulting in O(n^2) total time.

Space

O(n^2)

The hash map stores counts of all possible sums of pairs from nums1 and nums2, which can be up to O(n^2) in the worst case. This auxiliary space is necessary to achieve the time complexity improvement.

Solution

1class Solution:
  def fourSumCount(self, nums1, nums2, nums3, nums4):
3
      pair_count = {}
      result = 0
6
      for a in nums1:
          for b in nums2:
              pair_sum = a + b
              pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1
11
      for c in nums3:
          for d in nums4:
              target = -(c + d)
              if target in pair_count:
                  result += pair_count[target]
17
      return result

Step-by-Step Solution

1

Build frequency map of sums from nums1 and nums2 pairs

4pair_count = {}
5result = 0
7for a in nums1:
8    for b in nums2:
9        pair_sum = a + b
10        pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1

Objective

To count how many times each possible sum of elements from nums1 and nums2 occurs.

Key Insight

Precomputing sums of pairs from the first two arrays and storing their frequencies in a hash map enables constant-time lookups later. This reduces the problem's complexity by collapsing two nested loops into a single data structure that summarizes all pair sums.

Interview Quick-Check

Core Logic

The hash map stores sums of pairs from nums1 and nums2 as keys and their occurrence counts as values, enabling O(1) complement lookups.

State & Boundaries

Iterate over every element in nums1 and nums2 to cover all pair sums, ensuring completeness.

Common Pitfalls & Bugs

Forgetting to increment the count correctly or initializing counts improperly can lead to incorrect frequency tallies.

2

Accumulate counts of complementary sums from nums3 and nums4 pairs

12for c in nums3:
  for d in nums4:
      target = -(c + d)
      if target in pair_count:
          result += pair_count[target]

Objective

To find and sum the counts of pairs from nums3 and nums4 whose negated sums exist in the precomputed hash map.

Key Insight

By iterating over all pairs from nums3 and nums4 and checking if the negated sum exists in the hash map, the algorithm efficiently counts all quadruples summing to zero. This leverages the precomputed frequencies to avoid redundant computations.

Interview Quick-Check

Core Logic

For each sum of pairs from nums3 and nums4, check if its negation exists in the hash map and add the corresponding frequency to the result.

State & Boundaries

Iterate over all pairs in nums3 and nums4 to ensure all possible complementary sums are considered.

Common Pitfalls & Bugs

Neglecting to negate the sum or failing to check the hash map before adding to the result can cause incorrect counts.

3

Return the total count of quadruples summing to zero

18	`return result`

Objective

To output the final count of all quadruples (i, j, k, l) where the sum of elements equals zero.

Key Insight

After accumulating counts from all complementary pairs, returning the result completes the solution. This final step delivers the answer computed efficiently by the previous steps.

Interview Quick-Check

Core Logic

Return the accumulated count representing the total number of quadruples summing to zero.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 10 Critical

pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1

Increment the count of this sum in the hash map.

This line's placement and use of get with default zero ensures accurate frequency counting, which is fundamental to the algorithm's correctness and efficiency.

Line 16 Critical

result += pair_count[target]

Add the frequency of the complementary sum to the result.

This line is critical because it aggregates the counts of all valid quadruples, directly contributing to the final answer.

Line 4 Core

pair_count = {}

Initialize a hash map to store sums of pairs from nums1 and nums2.

This data structure is essential for counting frequencies of pair sums, enabling constant-time lookups for complements later.

Line 15 Core

if target in pair_count:

Check if the negated sum exists in the hash map.

This conditional identifies whether there are pairs from nums1 and nums2 that complement the current pair to sum to zero.

Line 9 Core

pair_sum = a + b

Calculate the sum of the current pair from nums1 and nums2.

Computing the pair sum is the key step to building the frequency map of sums.

Line 14 Core

target = -(c + d)

Calculate the negated sum of the current pair from nums3 and nums4.

Negating the sum allows checking for complementary sums in the hash map that sum to zero with this pair.

Line 18 Standard

return result

Return the total count of quadruples summing to zero.

Returning the accumulated result completes the algorithm, providing the final answer to the problem.

Line 5 Standard

result = 0

Initialize the result counter to zero.

This variable accumulates the total count of quadruples that sum to zero, serving as the final output.

Line 7 Standard

for a in nums1:

Iterate over each element in nums1.

This loop enumerates all possible first elements of pairs to be summed with elements from nums2.

Line 8 Standard

for b in nums2:

Iterate over each element in nums2.

Nested iteration ensures all pairs from nums1 and nums2 are considered for sum calculation.

Line 12 Standard

for c in nums3:

Iterate over each element in nums3.

This loop enumerates all possible first elements of pairs to be summed with elements from nums4 for complement checking.

Line 13 Standard

for d in nums4:

Iterate over each element in nums4.

Nested iteration ensures all pairs from nums3 and nums4 are considered for complement sum calculation.

Test Your Understanding

Why does precomputing sums of pairs from two arrays and using a hash map reduce the problem from O(n^4) to O(n^2)?

Because it transforms the quadruple sum problem into two pair sum problems. By storing frequencies of sums from the first two arrays, the algorithm can find complements from the other two arrays in constant time per pair, avoiding the need to check all quadruples explicitly.

Don't just read it. Drill it.

Reconstruct 4Sum II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the 4Sum II drill

or drill a free problem

1	`class Solution:`
2	`def fourSumCount(self, nums1, nums2, nums3, nums4):`
3
4	`pair_count = {}`
5	`result = 0`
6
7	`for a in nums1:`
8	`for b in nums2:`
9	`pair_sum = a + b`
10	`pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1`
11
12	`for c in nums3:`
13	`for d in nums4:`
14	`target = -(c + d)`
15	`if target in pair_count:`
16	`result += pair_count[target]`
17
18	`return result`

4	`pair_count = {}`
5	`result = 0`
7	`for a in nums1:`
8	`for b in nums2:`
9	`pair_sum = a + b`
10	`pair_count[pair_sum] = pair_count.get(pair_sum, 0) + 1`

Problem

Example

Approach

Solution

Step-by-Step Solution

Build frequency map of sums from nums1 and nums2 pairs

Accumulate counts of complementary sums from nums3 and nums4 pairs

Return the total count of quadruples summing to zero

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.