3Sum

The problem

You are given an array nums of whole numbers (call its length n). Find every group of three numbers, taken from three different positions, whose sum is 0. Return each such group of values once.

Two groups count as the same if they hold the same three values, even when the values come from different positions. The groups, and the order inside each group, may come back in any order.

Example 1

Input: nums = [-3, 1, 2, -1, 0, 2]

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

−3 + 1 + 2 = 0 and −1 + 0 + 1 = 0. There are two 2s, so −3, 1, 2 can be built twice, but it is returned once.

nums

-301122-130425

Example 2

Input: nums = [1, 2, -4]

Output: []

The only group is 1 + 2 − 4 = −1, which is not 0.

Example 3

Input: nums = [0, 0, 0, 0]

Output: [[0, 0, 0]]

Many groups of positions give 0 + 0 + 0, but they all hold the same values.

Constraints

• 3 ≤ n ≤ 3,000
• −100,000 ≤ nums[i] ≤ 100,000

Clarifying questions

Do we return positions or values?

Values. That is what makes sorting safe here.

Can one value be used twice?

Only if it appears twice in the array. Each group uses three different positions.

How are repeats handled?

A group of values appears once in the output, however many ways it can be built.

How large is n?

Up to 3,000. So O(n²), about 9 million steps, is fine, but O(n³) is not.

Spot the pattern

Fix one number, and the problem becomes Two Sum on the rest: find two numbers that add up to minus the fixed one. On a sorted array, Two Sum is the two-pointer trick: one pointer at each end, and the sum tells you which one to move. Sorting also puts equal values side by side, which makes skipping repeats easy.

Solutions

Brute forceO(n³)Sort and two pointersO(n²)

Show all

A hash set for the third number also reaches O(n²), but removing repeated groups is messier. Sorting handles the search and the repeats at once.

Brute force O(n³)

The idea

Try every group of three positions i < j < k. If the three numbers add up to 0, sort the three values and put them in a set. Sorting the group makes [2, −3, 1] and [−3, 1, 2] look the same, so the set keeps only one copy.

It is correct, but the number of groups grows like n³.

Walkthrough

nums

-301122-130425

result (a set, so no repeats)

empty

1. result = set()
2. for i in range(len(nums)):
3. for j in range(i + 1, len(nums)):
4. for k in range(j + 1, len(nums)):
5. if nums[i] + nums[j] + nums[k] == 0:
6. result.add(tuple(sorted((nums[i], nums[j], nums[k]))))
7. return [list(triple) for triple in result]

Try every group of three positions i < j < k. With 6 numbers that is 20 groups.

← BackStep →Play1 / 21

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: try every group of three positions.
    // About n^3 / 6 groups, so O(n^3) time. A set drops repeated triples.
    public List<List<Integer>> threeSum(int[] nums) {
        int numsLength = nums.length;
        Set<List<Integer>> result = new HashSet<>();
        for (int i = 0; i < numsLength; i++) {
            for (int j = i + 1; j < numsLength; j++) {
                for (int k = j + 1; k < numsLength; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        // Sorting the triple makes equal triples look the same.
                        List<Integer> triple = new ArrayList<>(List.of(nums[i], nums[j], nums[k]));
                        Collections.sort(triple);
                        result.add(triple);
                    }
                }
            }
        }
        return new ArrayList<>(result);
    }
}

Big O

Time O(n³)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line adds three numbers and compares the sum with 0. It sits inside three loops. When the sum is 0, sorting three values and adding them to the set is also a fixed amount of work. So each run is 1 step.

   1. result = set()
   2. for i in range(len(nums)):
   3. for j in range(i + 1, len(nums)):
   4. for k in range(j + 1, len(nums)):
   5. if nums[i] + nums[j] + nums[k] == 0:
   6. result.add(tuple(sorted((nums[i], nums[j], nums[k]))))
   7. return [list(triple) for triple in result]

2. 2 Count the runs on Example 1

   Example 1 has 6 numbers. With i = 0, the inner two loops pick 2 of the 5 numbers after it: 10 groups. With i = 1 it is 6, then 3, then 1.

   10 + 6 + 3 + 1 = 20 runs.

   i	0	1	2	3
   groups with this i	10	6	3	1

   total

   10 + 6 + 3 + 1 = 20

3. 3 Write the count for any n

   The loops visit every way to choose 3 positions out of n:

   n × (n − 1) × (n − 2) / 6 = ⅙n³ − ½n² + ⅓n

   Check it with Example 1: 6 × 5 × 4 / 6 = 20.

4. 4 Keep only the part that grows fastest

   • Drop the −½n² and +⅓n. Next to ⅙n³ they soon stop mattering.
   • Drop the ⅙. It does not change how fast the count grows. When n doubles, the work grows 8 times either way.

   What is left is n³. At n = 3,000 that is about 4.5 billion groups.

   So the time is O(n³).

5. S Space: count the extra memory the same way

   Besides the answer, the code keeps i, j and k. The set is the answer, which does not count as extra memory. So the space is O(1).

   result (the answer)ijk

Sort and two pointers O(n²)

The idea

Sort the array. Then fix the first number of the group, nums[i], from left to right. For each one, look for two numbers after it that add up to −nums[i].

Put left just after i and right at the end. Look at the sum of the three:

• Too small: nums[right] is already the biggest number left, so left must grow. Move left one step to the right.
• Too big: nums[left] is already the smallest number left, so right must shrink. Move right one step to the left.
• Zero: record the group, then move both pointers inward.

Two small checks handle repeats. Skip a fixed number equal to the one before it, since it would find the same groups. After a match, skip any left value equal to the one just used. And once nums[i] is above 0, stop: everything after it is positive too.

Why it never misses a group: each move only throws away a number that cannot be in any zero-sum group with the current nums[i], so no group is skipped.

Walkthrough

nums

-301122-130425

sorted

-30-1102132425

result

empty

1. nums.sort(); result = []
2. for i in range(len(nums) - 2):
3. if nums[i] > 0: break
4. if i > 0 and nums[i] == nums[i - 1]: continue
5. left, right = i + 1, len(nums) - 1
6. while left < right:
7. total = nums[i] + nums[left] + nums[right]
8. if total < 0: left += 1
9. elif total > 0: right -= 1
10. else:
11. result.append([nums[i], nums[left], nums[right]])
12. left += 1; right -= 1
13. while left < right and nums[left] == nums[left - 1]: left += 1
14. return result

Sort first. Equal numbers become neighbors, and the two-pointer trick needs order.

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort, fix one number, then find the other two with two pointers.
    // n fixed numbers times an O(n) scan, so O(n^2) time. Sorting is O(n log n).
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int numsLength = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numsLength - 2; i++) {
            // Everything after a positive number is positive too: no zero sum left.
            if (nums[i] > 0) break;
            // The same fixed number would find the same triples again.
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = numsLength - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                // Sorted order tells us which pointer to move.
                if (total < 0) left++;
                else if (total > 0) right--;
                else {
                    result.add(List.of(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    // Skip equal values, so the same pair is not used twice.
                    while (left < right && nums[left] == nums[left - 1]) left++;
                }
            }
        }
        return result;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two things cost time. The sort at the start takes about n log n steps. Then, for each fixed i, the while loop adds three numbers and moves at least one pointer. Each run is 1 step.

   1. nums.sort(); result = []
   2. for i in range(len(nums) - 2):
   3. if nums[i] > 0: break
   4. if i > 0 and nums[i] == nums[i - 1]: continue
   5. left, right = i + 1, len(nums) - 1
   6. while left < right:
   7. total = nums[i] + nums[left] + nums[right]
   8. if total < 0: left += 1
   9. elif total > 0: right -= 1
   10. else:
   11. result.append([nums[i], nums[left], nums[right]])
   12. left += 1; right -= 1
   13. while left < right and nums[left] == nums[left - 1]: left += 1
   14. return result

2. 2 Count the runs on Example 1

   Example 1 has 6 numbers. The sort takes about 6 × log₂ 6 ≈ 16 steps. Then the while loop runs 3 times for i = 0, 3 times for i = 1 and 2 times for i = 2. At i = 3 the fixed number is positive, so the loop stops.

   About 16 + 8 = 24 steps.

   i	0	1	2	3
   nums[i]	-3	-1	0	1
   while runs	3	3	2	stop

   total

   sort ≈ 16, then 3 + 3 + 2 = 8

3. 3 Write the count for any n

   For a fixed i, the gap between left and right starts at n − i − 2 and every run shrinks it by at least 1. Adding that up for every i:

   n log n + (n − 2) + (n − 3) + … + 1 ≈ n log n + ½n²

   Check it with Example 1: the gaps start at 4, 3 and 2, so at most 9 runs. The real 8 runs is just below that.

4. 4 Keep only the part that grows fastest

   • Drop the n log n. The sort is smaller than n² for any large n, so the pointer loops are the biggest part.
   • Drop the ½. It does not change how fast the count grows.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps i, left, right and total, a fixed few numbers. The answer does not count, so the space is O(1), plus whatever your language’s sort uses inside.

   result (the answer)ileftrighttotal

Common mistake

Skipping repeats only for the fixed number

Skipping equal nums[i] values is not enough. With [-2, 0, 0, 2, 2], after finding −2, 0, 2 the next left is another 0 and the next right is another 2, and the same group is recorded again. Also skip equal left values right after a match.

Tested at the limits

2,000 random arrays of 3 to 9 numbers from −4 to 4, so zeros, repeats and repeated triples are common. The brute force and the sort and two pointers gave the same triples every time.

Largest inputs	Result
3,000 numbers (the most allowed), all odd, so no triple adds to 0 and the pointers scan the whole range each time. Sort and two pointers.	0.3 s, and about 0.01 MB of extra memory: it sorts in place, and the sort borrows a little room of its own.
200 numbers. Brute force, about 1.3 million triples.	0.06 s. At 3,000 numbers it would check 4.5 billion triples, which is why the two pointers matter.