{ }SolveLogs
⌕
Home / Arrays & Hashing / #18
LeetCode #18 Medium

4Sum

4Sum is LeetCode 18 (Medium), and the 4sum leetcode problem is the fourth rung of the k-sum ladder. You get an integer array nums and an integer target, and must return every unique quadruplet of values that adds up to exactly target.

  • The four values come from four different positions a, b, c and d; no position is reused.
  • Each quadruplet is reported once. The same four values in a different order count as the same answer.
  • The quadruplets, and the values inside each one, may be returned in any order.

The array holds at most 200 numbers, so an O(n³) scan is about 8 million steps and comfortable. The values reach 10⁹, so four of them can sum past the 32-bit range.

Constraints
  • 1 <= nums.length <= 200
  • -10⁹ <= nums[i] <= 10⁹
  • -10⁹ <= target <= 10⁹
arraytwo-pointerssorting
Open on LeetCode ↗
02

Intuition

4Sum is 3Sum with one more loop in front. On a sorted array, two pointers starting at the ends find a pair with a given sum in one linear sweep: a total that is too small can only grow by moving the left pointer, and one that is too big can only shrink by moving the right.

So fix the first two values with nested loops, and the remaining two must add up to target minus those. That is one O(n) sweep per pair, giving O(n³). Sorting also puts equal values next to each other, which is what makes uniqueness a matter of stepping over neighbours rather than keeping a set.

How to spot this pattern

This is the k-sum template: sort, fix k − 2 values with nested loops, and finish the innermost pair with converging pointers, for O(n^(k−1)). Two Sum on a sorted array is the base case, 3Sum adds one loop, 4Sum adds two, and each new loop needs its own duplicate skip comparing against the previous value at that level.

03

Approach

Try it first

Before reading on, sort [1, 0, -1, 0, -2, 2] with target = 0 and run the two pointers by hand for the first pair. Then work out why [-2, 0, 0, 2] is reported once rather than twice. Aim for O(n³) time.

1

Sort the array

O(n log n), and it earns its cost twice over. Pointer moves now change the sum in a known direction, and equal values become neighbours, so duplicates can be skipped in place instead of filtered through a set at the end.

2

Fix the first two values

Loop i over the array and j from i + 1, skipping repeats:

  • skip i when it equals nums[i - 1].
  • skip j when it equals nums[j - 1] and j > i + 1.

Without that second guard the first j is thrown away whenever it happens to equal nums[i], losing real answers.

3

Close the remaining pair with two pointers

Set l = j + 1 and r = n - 1, and compare the four-value sum against target:

  • below target – move l right for a bigger value.
  • above target – move r left for a smaller one.
  • equal – record it, then move both ends inward.
4

Move both ends after a match, then skip repeats

Once a quadruplet is recorded the pair is spent, so:

  • advance l and retreat r together – moving only one re-tests a combination already stored.
  • then step l past any value equal to the one just used, and r likewise, or the same quadruplet comes out again.
5

Why no quadruplet is missed

When the sum is too small, nums[l] paired with the largest value left still falls short, so it can partner with nothing in the window and is safely discarded. The mirror argument discards nums[r] when the sum is too big, so every move drops only values that cannot be part of an answer.

6

Widen the sum before adding

Four values near 10⁹ exceed a signed 32-bit integer, and the wrap-around turns a large positive sum negative, which sends the pointers the wrong way. In C++ and Java cast to 64-bit before the first addition; Python's integers are unbounded.

04

4Sum solution in Python | C++ | Java

▶1class Solution:
▶2 def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
▶3 nums.sort()
▶4 n, res = len(nums), []
▶5 for i in range(n - 3):
▶6 if i > 0 and nums[i] == nums[i - 1]:
▶7 continue
▶8 for j in range(i + 1, n - 2):
▶9 if j > i + 1 and nums[j] == nums[j - 1]:
▶10 continue
▶11 l, r = j + 1, n - 1
▶12 while l < r:
▶13 s = nums[i] + nums[j] + nums[l] + nums[r]
▶14 if s < target:
▶15 l += 1
▶16 elif s > target:
▶17 r -= 1
▶18 else:
▶19 res.append([nums[i], nums[j], nums[l], nums[r]])
▶20 l += 1
▶21 r -= 1
▶22 while l < r and nums[l] == nums[l - 1]:
▶23 l += 1
▶24 while l < r and nums[r] == nums[r + 1]:
▶25 r -= 1
▶26 return res
sorted-2-10012foundnone yetsorted, target 0
nums[-2, -1, 0, 0, 1, 2]sorted
target0
Sort first. On a sorted array a sum that is too small can only grow by taking a bigger value from the left, and one that is too big can only shrink from the right, which is what makes the two-pointer sweep valid. Sorting also puts equal values side by side, so duplicates can be stepped over.
sorted-2-10012ijlrsum-2+-1+0+2<-1target 0foundnone yetneed 3 from the rest
fixed-2 + -1positions i and j
need3from the two pointers
Fix -2 and -1. The other two values must add up to 3, which the pointers l and r now hunt for in the stretch after j, closing in from both ends.
sorted-2-10012ijlrsum-2+-1+0+2<-1target 0foundnone yetsum too small, move l right
sum-1-2+-1+0+2
target0sum is short by 1
The sum is -1, below the target. Even paired with the largest value left, 0 cannot reach 0, so it is discarded and l steps right to a bigger number.
sorted-2-10012ijlrsum-2+-1+0+2<-1target 0foundnone yetsum too small, move l right
sum-1-2+-1+0+2
target0sum is short by 1
The sum is -1, below the target. Even paired with the largest value left, 0 cannot reach 0, so it is discarded and l steps right to a bigger number.
sorted-2-10012ijlrsum-2+-1+1+2=0target 0found-2-112match: -2, -1, 1, 2
sum0equals the target
found[-2, -1, 1, 2]1 so far
Match. -2 + -1 + 1 + 2 = 0, so the quadruplet is recorded. Both ends now move inward, because this pair is spent and keeping either one would only re-test a combination already stored.
sorted-2-10012ijlrsum-2+0+0+2=0target 0found-2-112need 2 from the rest
fixed-2 + 0positions i and j
need2from the two pointers
Fix -2 and 0. The other two values must add up to 2, which the pointers l and r now hunt for in the stretch after j, closing in from both ends.
sorted-2-10012ijlrsum-2+0+0+2=0target 0found-2-112-2002match: -2, 0, 0, 2
sum0equals the target
found[-2, 0, 0, 2]2 so far
Match. -2 + 0 + 0 + 2 = 0, so the quadruplet is recorded. Both ends now move inward, because this pair is spent and keeping either one would only re-test a combination already stored.
sorted-2-10012ijfound-2-112-2002skip repeat at j
i-2fixed
j3value 0, same as before
Position j repeats the value 0 inside the same i, so this pair was already tried. The guard only fires from the second turn of the inner loop, or a value equal to i's would be thrown away wrongly.
sorted-2-10012ijlrsum-1+0+0+2>1target 0found-2-112-2002need 1 from the rest
fixed-1 + 0positions i and j
need1from the two pointers
Fix -1 and 0. The other two values must add up to 1, which the pointers l and r now hunt for in the stretch after j, closing in from both ends.
sorted-2-10012ijlrsum-1+0+0+2>1target 0found-2-112-2002sum too big, move r left
sum1-1+0+0+2
target0over by 1
The sum is 1, above the target. Even with the smallest value left, 2 overshoots 0, so it is discarded and r steps left to a smaller number.
sorted-2-10012ijlrsum-1+0+0+1=0target 0found-2-112-2002-1001match: -1, 0, 0, 1
sum0equals the target
found[-1, 0, 0, 1]3 so far
Match. -1 + 0 + 0 + 1 = 0, so the quadruplet is recorded. Both ends now move inward, because this pair is spent and keeping either one would only re-test a combination already stored.
sorted-2-10012ijfound-2-112-2002-1001skip repeat at j
i-1fixed
j3value 0, same as before
Position j repeats the value 0 inside the same i, so this pair was already tried. The guard only fires from the second turn of the inner loop, or a value equal to i's would be thrown away wrongly.
sorted-2-10012ijlrsum0+0+1+2>3target 0found-2-112-2002-1001need 0 from the rest
fixed0 + 0positions i and j
need0from the two pointers
Fix 0 and 0. The other two values must add up to 0, which the pointers l and r now hunt for in the stretch after j, closing in from both ends.
sorted-2-10012ijlrsum0+0+1+2>3target 0found-2-112-2002-1001sum too big, move r left
sum30+0+1+2
target0over by 3
The sum is 3, above the target. Even with the smallest value left, 2 overshoots 0, so it is discarded and r steps left to a smaller number.
sorted-2-10012found-2-112-2002-1001return 3 quadruplets
answer[[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]3 unique
Return [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]. Every pair of fixed values was tried once, and each one cost a single sweep of the pointers, so the whole search is O(n³) after the sort.
05

Common pitfalls

Skipping the second index without the j > i + 1 guard

✗ Wrong
if nums[j] == nums[j - 1]:
    continue
✓ Right
if j > i + 1 and nums[j] == nums[j - 1]:
    continue

On the first turn of the inner loop nums[j - 1] is nums[i], so an equal pair is thrown away and quadruplets holding three equal values are lost. Each level's skip must only fire for repeats within that level.

Overflow on the sum in fixed-width languages

✗ Wrong
int s = nums[i] + nums[j] + nums[l] + nums[r];
✓ Right
long long s = (long long)nums[i] + nums[j] + nums[l] + nums[r];

Four values near 10⁹ exceed a signed 32-bit integer and wrap to a negative number, so the comparison with target sends the pointers the wrong way. The widening has to happen before the first addition, not on the result.

Moving only one pointer after recording a match

✗ Wrong
res.append([...])
l += 1
✓ Right
res.append([...])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
    l += 1
while l < r and nums[r] == nums[r + 1]:
    r -= 1

The current pair is used up, so both ends have to move. Advancing one alone keeps re-testing combinations already recorded, and without the skip loops equal neighbours emit the same quadruplet again.

06

Edge cases

Fewer than four numbers, e.g. [1, 2, 3]

The outer loop range is empty, so no quadruplet is formed and the result is [].

All values identical, e.g. [2, 2, 2, 2, 2] with target = 8

One quadruplet [2, 2, 2, 2]. The skips at i and j stop the other overlapping choices being reported.

Values near 10⁹

Their sum passes the 32-bit limit, so C++ and Java must add in 64-bit; Python is unaffected.

07

Complexity

Time
O(n³)
Space
O(1) extra
The 4sum time complexity is O(n³): two nested loops each run up to n times and every pair costs one linear two-pointer sweep, so O(n³) dominates the O(n log n) sort. Beyond the output, only the four indices are stored, though the sort itself may use O(log n) to O(n) depending on the language.
08

4Sum FAQ

Can 4Sum be solved faster than O(n³)?

The 4sum python code above is the standard answer, and there is an O(n²) variant that hashes every pair sum, but deduplicating the quadruplets it produces is awkward and it costs O(n²) memory. With n capped at 200 the sorted two-pointer version is fast enough and far easier to get right.

Why must duplicates be skipped at all four positions?

Each position independently chooses a value, so a repeat at any one of them produces the same quadruplet again. Skipping only at i and j still lets the inner pointers land on equal values and emit a duplicate.

← Prev · #17
Letter Combinations of a Phone Number
Next · #19 →
Remove Nth Node From End of List