4Sum — LeetCode 18
4Sum — LeetCode 18
Find all unique quadruplets in an array that sum to a given target. Master the reduce-by-two-pointers pattern — the same intuition behind 3Sum, extended one level deeper.
Time
O(n³)
Space
O(1)
Difficulty
Medium
Pattern
Two Pointers
Companies
Google · Amazon · Adobe
Problem statement
Given an array nums of n integers and an integer target,
return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
• 0 <= a, b, c, d < n
• a, b, c, d are distinct indices
• nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order. The result must not contain duplicate quadruplets.
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: After sorting → [-2,-1,0,0,1,2].
Three unique quadruplets sum to 0:
-2+(-1)+1+2 = 0 | -2+0+0+2 = 0 | -1+0+0+1 = 0
Example 2
Input
nums = [2,2,2,2,2], target = 8
Output
[[2,2,2,2]]
Explanation: Only one unique quadruplet exists even though the value 2 appears five times.
Duplicate-skip logic collapses all repeats into a single result.
Pointer movement
Sorted array:
[-2, -1, 0, 0, 1, 2] target = 0
■ i — outer fix
■ j — inner fix
■ L — left ptr
■ R — right ptr
Step 1 — i=0(-2), j=1(-1), L=2(0), R=5(2) → sum=-1 < 0 → move L right
i
-2
[0]
j
-1
[1]
L
0
[2]
0
[3]
1
[4]
R
2
[5]
-2 + (-1) + 0 + 2 = -1 < target(0) → L++
Step 2 — L=4(1), R=5(2) → sum=0 ✓ FOUND [-2,-1,1,2]
i
-2
[0]
j
-1
[1]
0
[2]
0
[3]
L
1
[4]
R
2
[5]
-2 + (-1) + 1 + 2 = 0 ✓ → Record [-2,-1,1,2]
Step 3 — j=2(0), L=3(0), R=5(2) → sum=0 ✓ FOUND [-2,0,0,2]
i
-2
[0]
-1
[1]
j
0
[2]
L
0
[3]
1
[4]
R
2
[5]
-2 + 0 + 0 + 2 = 0 ✓ → Record [-2,0,0,2]
Step 4 — i=1(-1), j=2(0), L=3(0), R=4(1) → sum=0 ✓ FOUND [-1,0,0,1]
-2
[0]
i
-1
[1]
j
0
[2]
L
0
[3]
R
1
[4]
2
[5]
-1 + 0 + 0 + 1 = 0 ✓ → Record [-1,0,0,1] · Done!
Intuition & approach
Core insight: Reduce 4Sum → 3Sum → 2Sum.
Fix two outer pointers with nested loops, then use a two-pointer sweep on the remaining subarray.
Sorting enables both the two-pointer technique and O(1) duplicate skipping.
1
Sort the array
Call
Arrays.sort(nums). This enables two-pointer convergence (sorted order guarantees that moving L right increases the sum, moving R left decreases it) and makes duplicate detection trivial — equals-previous means skip.
2
Fix
i — first outer loop
Iterate
i from 0 to n-4. If i > 0 and nums[i] == nums[i-1], skip — we've already explored all quadruplets starting with this value. This prevents duplicate quadruplets at the first position.
3
Fix
j — second outer loop
Iterate
j from i+1 to n-3. Skip duplicates with: if j > i+1 and nums[j] == nums[j-1]. Note the guard is j > i+1 not j > 0 — we only skip when it's not the very first j in this i iteration.
4
Two-pointer sweep:
L and R
Set
· sum == target → record, skip inner duplicates on both sides, advance both pointers.
· sum < target →
· sum > target →
L = j+1, R = n-1. While L < R:· sum == target → record, skip inner duplicates on both sides, advance both pointers.
· sum < target →
L++ (need bigger value).· sum > target →
R-- (need smaller value).
5
Guard against integer overflow
With constraints up to
10⁹, four values can sum to 4×10⁹ — well beyond int range (~2.1×10⁹). Cast at least one operand to long before any addition: (long)nums[i] + nums[j] + nums[L] + nums[R].
Common mistake: Using
j > 0 instead of j > i+1 for the j-duplicate skip. This incorrectly skips the very first j value after i, causing missed results.
Java solution — optimal two-pointer
import java.util.*; class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); // O(n log n) List<List<Integer>> result = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 3; i++) { // Skip duplicate values for i if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < n - 2; j++) { // Skip duplicate values for j (guard: j > i+1, not j > 0) if (j > i + 1 && nums[j] == nums[j - 1]) continue; int left = j + 1, right = n - 1; while (left < right) { // Cast to long — prevents integer overflow long sum = (long) nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); // Skip duplicates for left pointer while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates for right pointer while (left < right && nums[right] == nums[right - 1]) right--; left++; // Move both inward after recording right--; } else if (sum < target) { left++; // Sum too small → grow it } else { right--; // Sum too large → shrink it } } } } return result; } }
Bonus — generalised K-Sum (recursive)
The two-pointer pattern extends cleanly to any K. Fix k-2 pointers recursively, then apply two-pointer at depth 2. This single function handles 2Sum, 3Sum, 4Sum — and beyond.
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); return kSum(nums, (long) target, 0, 4); } private List<List<Integer>> kSum(int[] nums, long target, int start, int k) { List<List<Integer>> res = new ArrayList<>(); if (start == nums.length || k < 2) return res; if (k == 2) { // Base case: classic two-pointer int l = start, r = nums.length - 1; while (l < r) { long sum = nums[l] + nums[r]; if (sum == target) { res.add(new ArrayList<>(Arrays.asList(nums[l++], nums[r--])); } else if (sum < target) l++; else r--; while (l < r && l > start && nums[l] == nums[l-1]) l++; while (l < r && r < nums.length-1 && nums[r] == nums[r+1]) r--; } return res; } for (int i = start; i < nums.length - k + 1; i++) { if (i > start && nums[i] == nums[i - 1]) continue; for (List<Integer> subset : kSum(nums, target - nums[i], i + 1, k - 1)) { subset.0.add(0, nums[i]); // prepend current element res.add(subset); } } return res; } }
Approach comparison
| Approach | Time | Space | Notes |
|---|---|---|---|
| Sort + Two Pointers ✓ | O(n³) | O(1) | Optimal. What LeetCode expects. Handles duplicates cleanly. |
| Fix 2 + HashMap | O(n³) | O(n) | Same time. Extra space. Dedup via Set of Lists is slower. |
| Recursive K-Sum | O(n³) | O(n) | Elegant. Generalises to any K. Slightly more call-stack overhead. |
| 4 Nested Loops | O(n⁴) | O(1) | TLE beyond n≈50. Only useful for tiny inputs. |