AlgoViz
HomeTwo Pointers

3Sum

Medium

Find all unique triplets that sum to zero

In simple words

Sort first, then pick one number and use two fingers on the rest to find two more that add up to zero.

The idea

Sort the array. Fix each value in turn, then use two pointers on the rest to find pairs that complete the triplet to zero. Skipping duplicates keeps the results unique.

The trick

  • Sorting is what makes duplicate-skipping and the inner two-pointer sweep possible.
-1
0
1
2
-1
0
1
2
3
4

Step 1 of 12. Brute force: test every triple to see if it adds to 0. Values: -1, 0, 1, 2, -1.

1/12
Brute force
timeO(n³)spaceO(1)

Three nested loops.

1// try every triple2for (i) for (j>i) for (k>j)3  if (nums[i]+nums[j]+nums[k] === 0)4    record(i, j, k);

Input

array
[-1, 0, 1, 2, -1]

Memory

i
—
j
—
k
—
triples tried
—

Output

found
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [-1, 0, 1, 2, -1, -4]
Output:
[[-1, -1, 2], [-1, 0, 1]]
Explanation:
Triples that add to 0: [-1,-1,2] and [-1,0,1].

Example 2

Input:
nums = [0, 0, 0]
Output:
[[0, 0, 0]]
Explanation:
Only [0,0,0] sums to zero.

Example 3

Input:
nums = [1, 2, 3]
Output:
[]
Explanation:
No triple reaches 0, so none.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.