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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill 4Sum II and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →