3 Sum
Find every group of three numbers in an array that adds up to zero, each group listed once.
From an array of integers nums
Example 1
Output: [[-1, -1, 2], [-1, 0, 1]]
Example 2
Output: []
Explanation: no three numbers add up to 0.
Example 3
Output: [[0, 0, 0]]
The Idea
Picture six number cards on a table: -1, 0, 1, 2, -1 and -4. You may pick any three of them, and you want the picks that add up to 0. There are 20 ways to pick three cards out of six, and three of them work: the first -1 with 0 and 1, the second -1 with 0 and 1, and both -1s with 2.
Yet Example 1 lists only two triplets. The first two picks hold the same values, -1, 0 and 1, so they count as one triplet. That raises two questions: how do we find the triplets without trying every pick of three, and how do we report each one only once? With 3,000 numbers, there are about 4.5 billion picks of three.
Sorting helps with both. Sorted, the example reads -4, -1, -1, 0, 1, 2, and the two -1s now sit side by side. Sorted order also makes it quick to find two numbers with a given sum. Start one marker, lohilohi
Now fix the first number of a triplet with a third marker, iiilohii
In the first row, lohilohii
So a triplet is one fixed number plus a pair, and the pair is found by walking two markers toward each other instead of trying every pair. This way of searching is called the two-pointer technique. Finding a pair with a given sum in a sorted array is the problem
Solution Approach
Turning that idea into code means settling three things: how to pick the first number, how to search for the other two, and how to report each triplet only once.
Choosing the first number
Why not simply try every triplet? That takes three loops, one inside the other, and about 4.5 billion picks for 3,000 numbers. It also finds [-1, 0, 1] twice in Example 1, so a set would be needed to drop the repeat. Fixing one number and searching for the pair replaces the two inner loops with a single pass.
After sorting, one loop moves ilohiii
That gives a way to stop early. Once the number at ii
Searching for the other two
Where do lohiloihilohilohi
Why can a small sum safely leave the number at lohihii
Reporting each triplet only once
How do we report each triplet only once, when the array has repeated numbers? Sorting put equal numbers together, so a repeat always sits right after the number it repeats. If i
After a match, lohiilohihi
Java Solution
The method threeSum
- First, sort the input array with
, so equal numbers sit next to each other, and create the listArrays.sort(nums) for the triplets.result - A loop moves
along the array to choose the first number. It stops two places before the end, to leave room for the other two.i - Inside the loop, two checks come first. If
is above 0,nums[i] ends the loop, since no triplet can start here or later. Ifbreak equals the number before it,nums[i] moves on to the nextcontinue .i - Then search for the other two numbers:
starts atlo andi + 1 at the last position. Whilehi is left oflo , add the three numbers intohi . Too small movessum right, too big moveslo left.hi - When
is 0, add the three numbers tosum , move both markers inward, and moveresult past any copies of the value it just used.lo - When the loop is done, return
.result
The main[-2, 0, 0, 2, 2, -2][3, 1, 2]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break; // smallest of the three is positive: no sum of 0
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // same first value: same triplets again
}
int lo = i + 1;
int hi = nums.length - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) {
lo++; // too small: take a bigger second value
} else if (sum > 0) {
hi--; // too big: take a smaller third value
} else {
result.add(List.of(nums[i], nums[lo], nums[hi]));
lo++;
hi--;
while (lo < hi && nums[lo] == nums[lo - 1]) {
lo++; // skip repeats of the second value
}
}
}
}
return result;
}
public static void main(String[] args) {
System.out.println(threeSum(new int[] {-1, 0, 1, 2, -1, -4}));
System.out.println(threeSum(new int[] {0, 1, 1}));
System.out.println(threeSum(new int[] {0, 0, 0}));
System.out.println(threeSum(new int[] {0, 0, 0, 0, 0}));
System.out.println(threeSum(new int[] {-2, 0, 0, 2, 2, -2}));
System.out.println(threeSum(new int[] {3, 1, 2}));
}
}
Running it prints:
[[-1, -1, 2], [-1, 0, 1]]
[]
[[0, 0, 0]]
[[0, 0, 0]]
[[-2, 0, 2]]
[]
Look at the first line: [-1, 0, 1]nums[i] == nums[i - 1][[-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]
The fourth line comes from five zeros. There are 10 ways to pick three of them, and the line holds a single [0, 0, 0]
The fifth line shows why loilohilo[-2, 0, 2][[-2, 0, 2], [-2, 0, 2]]
The last line is empty. Sorted, [3, 1, 2][1, 2, 3]
The original implementation and its tests are on GitHub:
Complexity
The work is the sort, plus one pass of lohi
- Time: O(n²), where n is the length of the array. The loop over
runs up to n times, and each pass ofi andlo takes at most n steps. The sort, O(n log n), is small next to that.hi - Space: O(1) besides the output. The method keeps only
,i ,lo andhi , andsum sorts the array in place. That also means the caller's array comes back in sorted order.Arrays.sort
The same idea with one more fixed number solves