#15
3Sum
Medium Sort + two pointers
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all unique triplets in the array that add up to zero.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: all unique triplets that sum to 0.
Why this works: sort, fix the first number, and the rest is Two Sum II. Skip repeated values so triplets aren't duplicated.
Example: [-1, 0, 1, 2, -1, -4] sorted → [-4, -1, -1, 0, 1, 2]
fix -1: pointers find (-1, 2) and (0, 1)fix the second -1 → skipped (same value)result: [-1, -1, 2], [-1, 0, 1]
✦Hints open one at a time
Sort first. Fix one number, then the problem becomes Two Sum II on the rest.
Skip equal values for the fixed number and after finding a triplet, to avoid duplicates.
↗Approach
Sort. For each i (skipping repeats of nums[i]), run two pointers on i+1..end looking for -nums[i]. After a match, move both pointers past duplicates.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // same first number
if (nums[i] > 0) break; // all remaining are positive
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum < 0) l++;
else if (sum > 0) r--;
else {
res.add(Arrays.asList(nums[i], 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
Using a HashSet of lists to remove duplicates — it works but hides the cleaner skip logic and is slower.
Complexity
- Time: O(n²).
- Space: O(1) extra besides sorting and the output.
