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, return every group of three numbers, taken from three different positions, whose sum is 0. Such a group of three is called a triplet. A triplet with the same three values must appear only once, even if it can be picked from different positions. The array holds 3 to 3,000 numbers, and the triplets can come in any order.

Example 1
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Example 2
Input: nums = [0, 1, 1]
Output: []
Explanation: no three numbers add up to 0.
Example 3
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Solution

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, lo, at the smallest number and another, hi, at the largest. When their sum is too small, lo steps right to a bigger number. When it is too big, hi steps left to a smaller one.

Now fix the first number of a triplet with a third marker, i. With i on -4, the other two must add up to 4. The two largest numbers, 1 and 2, only make 3, so -4 starts no triplet. Move i to the first -1. The other two must now add up to 1, and lo and hi search for them among the numbers after i. Look at the picture below.

The sorted array -4, -1, -1, 0, 1, 2 with i on the first -1, so lo and hi need 1. First lo is on the second -1 and hi on 2: -1 + 2 = 1, a match, [-1, -1, 2]. Then lo is on 0 and hi on 1: 0 + 1 = 1, a match, [-1, 0, 1].

In the first row, lo is on the second -1 and hi on 2. Their sum is 1, a match: the triplet [-1, -1, 2]. Both markers move one step inward. In the second row, lo is on 0 and hi on 1, which make 1 again: the triplet [-1, 0, 1]. One more step and the markers pass each other, so the search for this i is over.

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 Two Sum II, and 3Sum runs that search once for each fixed number.

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 i over the array. lo and hi only look at positions after i, so the three positions are always different, and the number at i is the smallest of the three.

That gives a way to stop early. Once the number at i is above 0, the other two are at least as big, so the sum is above 0 too. Every later i is on a number at least as big, so the loop can end there.

Searching for the other two

Where do lo and hi start? lo starts just after i, and hi at the last position. While lo is left of hi, add the three numbers. A sum below 0 moves lo right, a sum above 0 moves hi left, and a sum of exactly 0 records the triplet and moves both.

Why can a small sum safely leave the number at lo behind? hi is already on the largest number still in range, and even that partner gives too little. No other partner can do better, so that number is finished. The same reasoning, turned around, covers hi on a big sum. Every step moves one marker inward, so a pass takes at most as many steps as there are numbers after i.

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 lands on the same value as the position before it, every triplet that value can start was found already, so the loop skips it. In the example, that skips the second -1.

After a match, lo moves past copies of the value it just used. hi needs no check of its own. With i fixed and lo on a new value, the number that completes the sum to 0 is a different value too, so a copy at hi gives a sum that is too big, and hi moves on.

Java Solution

The method threeSum works in these steps:

  1. First, sort the input array with Arrays.sort(nums), so equal numbers sit next to each other, and create the list result for the triplets.
  2. A loop moves i along the array to choose the first number. It stops two places before the end, to leave room for the other two.
  3. Inside the loop, two checks come first. If nums[i] is above 0, break ends the loop, since no triplet can start here or later. If nums[i] equals the number before it, continue moves on to the next i.
  4. Then search for the other two numbers: lo starts at i + 1 and hi at the last position. While lo is left of hi, add the three numbers into sum. Too small moves lo right, too big moves hi left.
  5. When sum is 0, add the three numbers to result, move both markers inward, and move lo past any copies of the value it just used.
  6. When the loop is done, return result.

The main method runs the three examples, an array of five zeros, the array [-2, 0, 0, 2, 2, -2], where the same pair could match twice, and [3, 1, 2], whose smallest number is already above 0.

Java
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:

Output
[[-1, -1, 2], [-1, 0, 1]]
[]
[[0, 0, 0]]
[[0, 0, 0]]
[[-2, 0, 2]]
[]

Look at the first line: [-1, 0, 1] appears once, although either -1 could start it. The check nums[i] == nums[i - 1] skips the second -1. Without that check, the same input prints [[-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 lo skips its copies. Sorted, that input is -2, -2, 0, 0, 2, 2. With i on the first -2, lo on the first 0 and hi on the second 2 make a match. One step inward, the second 0 and the first 2 would match again. lo moves past the second 0 instead, so [-2, 0, 2] is listed once. Without that skip, the line prints [[-2, 0, 2], [-2, 0, 2]].

The last line is empty. Sorted, [3, 1, 2] becomes [1, 2, 3], whose first number is already above 0, so the loop stops at its first step.

The original implementation and its tests are on GitHub: ThreeSum.java and TestThreeSum.java.

Complexity

The work is the sort, plus one pass of lo and hi for each first number.

  • Time: O(n²), where n is the length of the array. The loop over i runs up to n times, and each pass of lo and hi takes at most n steps. The sort, O(n log n), is small next to that.
  • Space: O(1) besides the output. The method keeps only i, lo, hi and sum, and Arrays.sort sorts the array in place. That also means the caller's array comes back in sorted order.

The same idea with one more fixed number solves 4Sum.