Faangprep Logo
Log inStart free
Browse curriculum

3-Sum

Find every group of three values, taken from different positions in the integer array nums, that adds up to 0, listing each distinct triplet once.

MediumSolve on LeetCode

Examples

Input:nums = [-1,0,1,2,-1,-4]
Output:[[-1,-1,2],[-1,0,1]]
Explain:

Two different triplets reach 0: [-1,0,1] and [-1,-1,2]. They may come back in any order, and so may the numbers inside each one.

Input:nums = [0,1,1]
Output:[]
Explain:

With exactly three numbers there is one triplet to try, and its sum is 2, not 0.

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

The only possible triplet sums to 0.

Problem Understanding

The goal is to find all unique triplets that sum to zero. It's essentially an extension of the Two Sum problem.

Key Constraint: The solution set must not contain duplicate triplets. This implies we need to be careful about how we select numbers.

Strategy: Reduce to Two Sum

We can fix one number, say nums[i]. Then the problem becomes finding two other numbers in the rest of the array that sum to -nums[i].

Since we want to avoid duplicates and use the Two Pointer technique efficiently, our first step is to sort the array.

Algorithm:

  1. Sort the array.
  2. Iterate through the array with index i.
  3. For each i, run the Two Sum (Sorted) logic on the remaining part of the array (i+1 to end) with target = -nums[i].

Interactive Visualization

The figure fixes i and moves the L and R pointers to find pairs summing to -nums[i]; recorded triplets collect beside it.

Dry Run Table

Input: nums = [-1, 0, 1, 2, -1, -4] -> Sorted: [-4, -1, -1, 0, 1, 2]

i (val) Left (val) Right (val) Sum Action
0 (-4) 1 (-1) 5 (2) -3 Too small. L++
... ... ... ... (No triplets for -4)
1 (-1) 2 (-1) 5 (2) 0 Match! Record [-1,-1,2]. L++, R--
1 (-1) 3 (0) 4 (1) 0 Match! Record [-1,0,1]. L++, R--
2 (-1) ... ... ... Skip duplicate i!
3 (0) 4 (1) 5 (2) 3 Too big.

Result: [[-1,-1,2], [-1,0,1]]

Edge Cases & Common Mistakes

Edge Cases:

  • Fewer than 3 elements: Impossible to find a triplet. Return empty.
  • No Solution: Return empty list.
  • All Zeros: Should return [[0,0,0]].

Common Mistakes:

  • Duplicate Triplets: The problem asks for unique triplets. You MUST skip duplicate values for both i and the two pointers L, R after finding a match.
  • Not Sorting: The Two Pointer logic for 3-Sum relies heavily on the array being sorted.

Solution

3-Sum Code
1/**
2 * @param {number[]} nums
3 * @return {number[][]}
4 */
5var threeSum = function(nums) {
6    nums.sort((a, b) => a - b);
7    const result = [];
8    
9    for (let i = 0; i < nums.length - 2; i++) {
10        if (i > 0 && nums[i] === nums[i - 1]) continue;
11        
12        let left = i + 1;
13        let right = nums.length - 1;
14        
15        while (left < right) {
16            const sum = nums[i] + nums[left] + nums[right];
17            
18            if (sum === 0) {
19                result.push([nums[i], nums[left], nums[right]]);
20                while (left < right && nums[left] === nums[left + 1]) left++;
21                while (left < right && nums[right] === nums[right - 1]) right--;
22                left++;
23                right--;
24            } else if (sum < 0) {
25                left++;
26            } else {
27                right--;
28            }
29        }
30    }
31    return result;
32};
Previous

Container With Most Water

Next

Valid Triangle Number

The approach, step by step

  1. Sort

    Sort the array so equal values sit together and the two-pointer scan works.

  2. Fix i

    For each i, skip it if it repeats the previous value, then set left = i + 1 and right = n - 1.

  3. Scan and record

    Move left in when the sum is below 0, right in when above; on 0, record the triplet and skip duplicates on both sides.

Frequently asked questions

How does 3Sum reduce to Two Sum?

After sorting, fix nums[i] and look for two later values summing to -nums[i]. That inner search is the sorted two-pointer scan, run once for each i.

How do you avoid duplicate triplets in 3Sum?

Skip an i whose value equals the previous one, and after recording a match move both pointers past any copies of their values. Sorting puts equal values next to each other, which makes both skips simple.

What is the time complexity of 3Sum?

O(n²): the sort is O(n log n) and the two-pointer scan for each of the n values of i is O(n). Extra space is the sort’s, O(log n), not counting the output.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description