AlgoViz
HomeArrays & Hashing

4 Sum

Medium

Two fixed elements, then two pointers

Problem

Given an integer array nums and an integer target. Return all quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: a, b, c, d are all distinct valid indices of nums. nums[a] + nums[b] + nums[c] + nums[d] == target. Notice that the solution set must not contain duplicate quadruplets. One element can be a part of multiple quadruplets. The output and the quadruplets can be returned in any order.

In simple words

Fix two numbers, then two-pointer the remaining pair — like 3-sum with one more layer.

The idea

The same ladder one rung higher: sort, fix two elements with nested loops, and two-point the remainder for the last pair. That gives O(n³), and the duplicate-skipping discipline has to be applied at all four levels.

The trick

  • Skip duplicates at each of the four positions independently.
  • Use 64-bit arithmetic — four values can overflow a 32-bit sum.
  • O(n³) time, O(1) space beyond the sort.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
-2
3
5
7
9
0
1
2
3
4
5

Step 1 of 2. Here's the example — nums = [1, -2, 3, 5, 7, 9], target = 7 Values: 1, -2, 3, 5, 7, 9.

1/2
Optimal
timeO(n^3)spaceO(1)
1sort(nums)2for i in 0..n-1: (skip duplicate i)3  for j in i+1..n-1: (skip duplicate j)4    lo = j+1, hi = n-15    while lo < hi:6      s = nums[i]+nums[j]+nums[lo]+nums[hi]7      if s == target: record; skip duplicates; lo++; hi--8      elif s < target: lo++9      else: hi--

Input

array
[1, -2, 3, 5, 7, 9]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 0, -1, 0, -2, 2], target = 0
Output:
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Explanation:
All unique quadruples summing to 0.

Example 2

Input:
nums = [2, 2, 2, 2, 2], target = 8
Output:
[[2, 2, 2, 2]]
Explanation:
Only [2,2,2,2] works.

Example 3

Input:
nums = [1, 2, 3, 4], target = 100
Output:
[]
Explanation:
Nothing reaches 100 → none.

Constraints

  • 1 <= nums.length <= 200
  • -10^4 <= nums[i] <= 10^4
  • -10^4 <= target <= 10^4

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.