AlgoViz
HomeArrays & Hashing

3 Sum

Medium

Sort, fix one, two-point the rest

Problem

Given an integer array nums. Return all triplets such that: i != j, i != k, and j != k nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. One element can be a part of multiple triplets. The output and the triplets can be returned in any order.

In simple words

Fix one number, then use two pointers from both ends to find the pair that completes zero.

The idea

Sort the array, fix each element in turn, and use two pointers on the remainder to find pairs completing the target. Sorting is what makes both the two-pointer sweep and the duplicate skipping possible, bringing O(n³) down to O(n²).

The trick

  • Skip duplicate values at every level or the same triple is emitted repeatedly.
  • Break out early once the fixed element is positive — nothing later can sum to zero.
  • O(n²) time, O(1) space beyond the sort.
-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)

Try every triple.

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.

Constraints

  • 1 <= nums.length <= 3000
  • -10^4 <= nums[i] <= 10^4

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

Finished the walkthrough? Add it to your streak.