MediumTwo Pointers
3Sum
Explanation & Solution
Description
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.
The solution set must not contain duplicate triplets.
Input:nums = [-1,0,1,2,-1,-4]
0
-1
1
0
2
1
3
2
4
-1
5
-4
Output: [[-1,-1,2],[-1,0,1]]
Explanation: The distinct triplets that sum to zero are [-1,-1,2] and [-1,0,1]. Notice that the order of the output and the order of the triplets does not matter.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Approach
Two Pointers pattern
1. Sort the Array
- Sort
numsin ascending order - This enables the two-pointer technique and makes duplicate skipping straightforward
2. Fix One Element
- Iterate index
ifrom0tonums.length - 3 nums[i]is the fixed element of the triplet- If
nums[i] === nums[i - 1], skip it to avoid duplicate triplets
3. Two-Pointer Search
- Set
left = i + 1andright = nums.length - 1 - Compute
sum = nums[i] + nums[left] + nums[right] - If
sum === 0: found a valid triplet, add it to the result - If
sum < 0: moveleftright to increase the sum - If
sum > 0: moverightleft to decrease the sum
4. Skip Duplicates After a Match
- After finding a valid triplet:
- Advance
leftpast all duplicate values - Retreat
rightpast all duplicate values - Then move both pointers one more step inward
- This ensures no duplicate triplet is added to the result
5. Return the Result
- After all iterations complete, return the
resultarray - Each triplet in the result is unique and sums to zero
Key Insight
- Sorting transforms this from an O(n³) brute-force into an O(n²) problem
- Fixing one element reduces 3Sum to a 2Sum problem on the remaining sorted subarray
- The two-pointer technique solves 2Sum in O(n) on a sorted array
- Careful duplicate skipping at both the outer loop and inner pointers guarantees uniqueness
Visualization
Input:
[-1, 0, 1, 2, -1, -4]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
11 steps