RTE logo
← Back to DSA map
Two Pointers

3Sum

All unique triplets that sum to zero.

Medium

Problem

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] with i, j, and k all different, such that nums[i] + nums[j] + nums[k] = 0.

  • Triplets must be unique - no duplicates in the result.
  • Order inside a triplet does not matter.
  • Order of the result does not matter.

Examples

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Input: nums = [0, 1, 1]
Output: []
No triplet sums to 0.
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]

Approach

Time O(n²)Space O(1) beyond sorting
  1. Sort the array so equal values sit together and sums move predictably.
  2. Fix nums[i] as the first number. Skip it if it equals nums[i - 1], and stop once nums[i] > 0 - nothing after it can bring the sum back to 0.
  3. Put L just after i and R at the end. If the sum is too small, move L right; if too big, move R left.
  4. On a match, record the triplet, then move L and R past any repeated values before continuing, so the same triplet is not recorded twice.

Brute force: Three loops inside each other, plus a set to throw away repeated triplets. On 1,000 numbers that is a billion steps.

Common mistakes

  • Skipping duplicates only for i is not enough: after a match, repeated values at L or R produce the same triplet again - e.g. [-2, 0, 0, 2, 2].
  • Deduplicating afterwards with JSON.stringify works, but hides the real fix and costs extra memory.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

3SUM
Solution · JS
Array · i=— L=— R=—
-10
01
12
23
-14
-45
sum will appear here
RESULT[ ]
i
—
L
—
R
—
Sum
—
Found
0
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...