← DSA Atlas
Dedicated problem page · #18

4Sum

MediumTwo PointersTwo fixed anchors plus a sorted two-pointer inner scanTwo pointers (after sorting)
Solve on LeetCode ↗
18
MediumTwo PointersTwo pointers (after sorting)Two fixed anchors plus a sorted two-pointer inner scan

4Sum

Given an integer array nums and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] with distinct indices such that the four values sum to target. The result must not contain duplicate quadruplets.

Open official problem prompt ↗
In plain English

List every distinct group of four values that add up to the given target, with no repeated group.

Picture it like this

Like 3Sum with an extra locked digit on a combination padlock: you fix the first two dials, then spin the last two from opposite ends until the whole combination matches the target.

Example
Input
nums = [1, 0, -1, 0, -2, 2], target = 0
Output
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Why
Each listed quadruplet sums to 0, and these are the only distinct value-combinations that do so.
Constraints
1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
Pattern lesson

See the pattern, then code

Two fixed anchors plus a sorted two-pointer inner scan
Recognition clue

It is the same shape as 3Sum but one dimension deeper: an order-independent combination hitting a fixed sum, so sort and reduce with nested anchors down to a two-pointer 2Sum.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Fix the two smallest elements with nested loops, then solve the remaining 2Sum on the sorted tail with converging pointers, skipping duplicates at every level.

New words, made simpleKnow these before the algorithm
Nested anchors
The two outer loop indices a and b that are held fixed while the inner pointers search.
Residual target
target - nums[a] - nums[b], the sum the two inner pointers must reach.
Multi-level dedup
Skipping equal values at the a, b, lo, and hi levels to avoid duplicate quadruplets.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Quadruple loop

Too slow and clumsy to deduplicate.

Check every combination of four indices.

Time O(n^4)Space O(n)
Best choiceSort + two anchors + two pointers

One order faster than brute force with clean in-place dedup; the standard optimal approach.

Fix a and b, then converge lo/hi over the tail for the residual target.

Time O(n^3)Space O(1)
The rule we keep true

Invariant

For fixed a and b, every pair in the tail that reaches the residual target lies between lo and hi, and sorted order guarantees a pointer move never discards a still-viable pair.

Why this is correct

Reasoning

Reducing to a sorted 2Sum makes each inner move eliminate exactly one impossible endpoint; the duplicate-skips at all four levels ensure that identical value-quadruplets are emitted only once even with repeated numbers.

The algorithm in three movesSay these aloud before coding
1Sort nums to enable pointer movement and dedup

sorted = [-2,-1,0,0,1,2]

2Loop a over the first index, skipping duplicate values

a=0(-2),b=1(-1) -> need 3 -> lo=4(1),hi=5(2) hit

3Loop b over the second index, skipping duplicate values

record [-2,-1,1,2]

4Run lo/hi pointers on the remainder toward target - nums[a] - nums[b], skipping duplicates on hits

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
-20
-11
02
03
14
25
1 · Read[1,0,-1,0,-2,2]
2 · AskOrder for scanning?
3 · Update state[-2,-1,0,0,1,2]
4 · ResultSorted ascending.
Key takeaway

With anchors -2 and -1 fixed, pointers land on 1 and 2 to complete the first zero-sum quadruplet.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-5Sort and init

    Sorting underpins both the pointer logic and duplicate skipping.

  2. 2
    Lines 6-11Two anchor loops

    Fix a and b, skipping repeated anchor values so groups are unique.

  3. 3
    Lines 12-19Inner two-pointer 2Sum

    Move lo/hi by the sign of total minus target to hit the residual.

  4. 4
    Lines 20-25Record and skip

    Store the quad and step both pointers past equal values.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Arrays shorter than 4 yield []
  • Large values with large target require no special overflow handling in Python
  • Many duplicates like [0,0,0,0] with target 0 give a single [0,0,0,0]
  • No valid quadruplet returns []
!

Common beginner mistakes

  • Missing the b-level duplicate skip (guard b > a+1) so duplicate quads leak
  • Off-by-one loop bounds (a up to n-4, b up to n-3 in index terms)
  • Comparing to a hardcoded 0 instead of the given target
Check your understanding

Why does the b-loop dedup use the guard b > a + 1 rather than b > 0?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#42Trapping Rain WaterConverging pointers tracking left/right maxima#75Sort ColorsDutch National Flag partition