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.

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

python

▶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

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.

06

Complexity

Time

O(n³)

Space

O(1)

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