Faangprep Logo
LoginRegister
Two Pointers
Medium

3-Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
10 min read
Solve on LeetCode
Examples
Input:nums = [-1,0,1,2,-1,-4]
Output:[[-1,-1,2],[-1,0,1]]
Explain:

The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.

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

The only possible triplet does not sum to 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
Step 1 / 5
i
-4
0
L
-1
1
-1
2
0
3
1
4
R
2
5

Sorted Array. Fix i = -4. Target = 4. L=-1, R=2. Sum = -4 + -1 + 2 = -3. Too small. Move L.

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep