LeetCode #18 Medium

4Sum

Return all unique quadruplets [a,b,c,d] in nums that sum to target.

arraytwo-pointerssorting

02

Intuition

3Sum is 'fix one, two-pointer the rest'. 4Sum is the same idea one level up: fix the first two numbers with nested loops, then close the remaining pair with converging pointers on the sorted array. Sorting is what makes both the pointer walk and duplicate-skipping possible.

How to spot this pattern

The k-sum recipe scaled up: sort, fix k - 2 indices with nested loops, two-pointer the innermost pair. Every level needs its own duplicate skip, and each skip guard compares against the previous element at that level. Once you see 3Sum and 4Sum as the same template with one more loop, 5Sum needs no new ideas.

03

Approach

1

Sort first

Sorting lets converging pointers steer by sum (too small → move left pointer up, too big → move right pointer down) and puts duplicates next to each other so they're easy to skip.

2

Fix i and j, two-pointer l and r

For each pair (i, j), find pairs (l, r) in the suffix with nums[l]+nums[r] == target − nums[i] − nums[j]. That inner search is linear.

3

Skip duplicates at every level

After using a value at position i, j, l, or r, advance past equal neighbours. This produces unique quadruplets without a set.

04

Solution & live demo

▶1class Solution:
▶2    def fourSum(self, nums, target):
▶3        nums.sort()
▶4        n, res = len(nums), []
▶5        for i in range(n - 3):
▶6            if i and nums[i] == nums[i-1]: continue
▶7            for j in range(i + 1, n - 2):
▶8                if j > i + 1 and nums[j] == nums[j-1]: continue
▶9                l, r = j + 1, n - 1
▶10                while l < r:
▶11                    s = nums[i] + nums[j] + nums[l] + nums[r]
▶12                    if s < target: l += 1
▶13                    elif s > target: r -= 1
▶14                    else:
▶15                        res.append([nums[i], nums[j], nums[l], nums[r]])
▶16                        l += 1
▶17                        while l < r and nums[l] == nums[l-1]: l += 1
▶18                        r -= 1
▶19                        while l < r and nums[r] == nums[r+1]: r -= 1
▶20        return res

05

Common pitfalls

Skipping duplicates on the second index with the wrong bound

✗ Wrong

if nums[j] == nums[j-1]: continue

✓ Right

if j > i + 1 and nums[j] == nums[j-1]: continue

Without the j > i + 1 guard the first candidate of the inner loop is skipped whenever it equals nums[i], so legitimate quadruples containing 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];

Python is safe, but four values near 10^9 exceed a 32-bit int and wrap to a negative — the pointers then move the wrong way. The widening has to happen before the additions.

Moving only one pointer after recording a hit

✗ Wrong

res.append([...])
l += 1

✓ Right

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

The current pair is spent, so both ends must move; advancing one alone re-tests a combination already recorded. The skip loops then step over the duplicate values that would produce identical quadruples.

06

Edge cases

Fewer than 4 elements

Loops never produce a quadruple; returns [].

Large values overflowing in other languages

Python ints are unbounded; elsewhere use 64-bit sums.

07

Complexity

Time

O(n³)

Space

O(1)

Two fixed indices × linear pointer sweep; sort is O(n log n).