Skip to main content

454. 4Sum II

medium

Given four equal-length integer arrays, count tuples (i, j, k, l) where A[i] + B[j] + C[k] + D[l] == 0. The textbook meet-in-the-middle: pre-compute pair sums from two arrays and look up the negation from the other two — O(n^2) total.

By Sam K., Founder, InterviewChamp.AI · Last verified

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: 0 <= i, j, k, l < n; and nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force is O(n^4). Meet-in-the-middle splits the problem into two halves.

Hint 2

Compute every pair sum a + b across A x B and count them in a hash map: pair_count[a + b] += 1.

Hint 3

Iterate every (c, d) in C x D; add pair_count[-(c + d)] to the answer.

Solution approach

Reveal approach

Meet-in-the-middle with a hash map. Walk nums1 x nums2 with nested loops; for each (a, b), increment pair_count[a + b]. Then walk nums3 x nums4; for each (c, d), add pair_count[-(c + d)] to the answer counter (lookups for missing keys default to 0). Return counter. Two halves each take O(n^2), so total is O(n^2) time and O(n^2) space for the map. The transformation 'find pair sum == -(c + d)' is what halves the brute force from O(n^4) to O(n^2). The same meet-in-the-middle trick generalizes to k-sum-style problems where k is even.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • hash-map
  • meet-in-the-middle
  • counting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta

More Hash Tables practice problems

See all Hash Tables problems →