#18
4Sum
Medium Sort + two pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all unique quadruplets that add up to target.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: unique quadruplets that hit a target.
Why this works: 3Sum with one more fixed number. Sorting and skipping duplicates keep results unique; use long for the sum.
Example: [1, 0, -1, 0, -2, 2], target 0 → sorted [-2, -1, 0, 0, 1, 2]
fix -2, -1: find (1, 2)fix -2, 0: find (0, 2)fix -1, 0: find (0, 1)
✦Hints open one at a time
It's 3Sum with one more outer loop.
Sums can exceed int range — use long.
↗Approach
Sort. Two nested loops fix the first two numbers (skipping duplicates), then two pointers find the remaining pair, skipping duplicates after each match.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
for (int a = 0; a < n - 3; a++) {
if (a > 0 && nums[a] == nums[a - 1]) continue;
for (int b = a + 1; b < n - 2; b++) {
if (b > a + 1 && nums[b] == nums[b - 1]) continue;
int l = b + 1, r = n - 1;
while (l < r) {
long sum = (long) nums[a] + nums[b] + nums[l] + nums[r];
if (sum < target) l++;
else if (sum > target) r--;
else {
res.add(Arrays.asList(nums[a], nums[b], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
}
}
}
return res;
}
}!Common mistake
Adding four ints in int — values up to 10^9 overflow. Cast to long.
Complexity
- Time: O(n³).
- Space: O(1) extra besides the output.
