A complete visual walkthrough of the sort + two pointer approach — from brute force to optimal O(n²) with duplicate handling.
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.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. 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.
Example 2:
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105The most obvious approach: try every combination of three distinct indices and check if they sum to zero. We also need a set to discard duplicate triplets.
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) for (int k = j + 1; k < n; k++) if (nums[i] + nums[j] + nums[k] == 0) result.add(sorted(i, j, k));
for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { for k := j + 1; k < n; k++ { if nums[i]+nums[j]+nums[k] == 0 { result = append(result, sorted(i, j, k)) } } } }
for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): if nums[i] + nums[j] + nums[k] == 0: result.append(sorted([i, j, k]))
for i in 0..n { for j in (i + 1)..n { for k in (j + 1)..n { if nums[i] + nums[j] + nums[k] == 0 { result.push(sorted_triple(i, j, k)); } } } }
for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) for (let k = j + 1; k < n; k++) if (nums[i] + nums[j] + nums[k] === 0) result.push(sorted(i, j, k));
For an array of length 3000 (a typical LeetCode constraint), this examines ~4.5 billion triplets. That's a guaranteed Time Limit Exceeded.
Can we do better? The 2Sum problem uses a hash map to go from O(n²) to O(n). What if we fix one number and solve 2Sum on the rest? That would give us O(n) × O(n) = O(n²). But there's an even cleaner way — sort first, then use two pointers.
Sort the array first. Then for each element nums[i], we need to find two numbers in the remaining subarray that sum to -nums[i]. Since the array is sorted, we can use two pointers converging from both ends.
i from index 0. We need nums[left] + nums[right] = -nums[i].left starts at i+1, right starts at end. If sum < 0, move left up. If sum > 0, move right down.Why does sorting help so much? In a sorted array, the two-pointer technique guarantees we visit each pair at most once: if the sum is too small, the only way to increase it is to move the left pointer right. If too large, move the right pointer left. No backtracking needed.
Let's trace through the example [-1, 0, 1, 2, -1, -4]. After sorting, we get:
Indices: 0 through 5. Now we fix each element and use two pointers on the rest.
Target for two pointers: -(-4) = 4. We need left + right = 4.
-1 + 2 = 1 < 4. Sum is too small, so move L right. After several steps, L and R cross without finding sum = 4. No triplets with -4.
Target: -(-1) = 1. We need left + right = 1.
After this, L and R cross. Move to next fixed element.
nums[2] == nums[1], so we skip this iteration entirely to avoid generating the same triplets we already found. This is the outer duplicate check.
Avoiding duplicate triplets is the trickiest part. There are three places where we must skip:
if (i > 0 && nums[i] == nums[i-1]) continue;while (left < right && nums[left] == nums[left+1]) left++;while (left < right && nums[right] == nums[right-1]) right--;Why three checks, not just a Set? Using a Set to de-duplicate works, but it adds O(n) space and hash overhead. The three skip checks are O(1) each and keep space at O(1) (excluding output). Since the array is sorted, identical values are adjacent — a simple comparison with the neighbor is all we need.
If nums.length < 3, it is impossible to form any triplet. Return an empty list immediately. The constraint guarantees at least 3 elements on LeetCode, but a guard is good practice.
[0, 0, 0]The only valid triplet is [0, 0, 0]. After sorting the array is still [0, 0, 0]; fix i = 0, set left = 1 and right = 2, sum equals zero, so [0, 0, 0] is added. The duplicate-skip logic then advances both pointers past each other, ending the inner loop — exactly one triplet is returned.
Arrays like [1, 2, 3] or [-5, -4, -3] produce no triplets summing to zero. The two-pointer scan exhausts without ever hitting sum == 0, and the result list stays empty.
[-2, 0, 0, 2, 2]Without deduplication this would emit [-2, 0, 2] twice. Sorting groups identical values together, and the three skip checks (outer i, inner left, inner right) ensure each unique triplet is collected exactly once.
If every element is negative (e.g., [-3, -2, -1]), the smallest possible sum of any three numbers is still negative — no triplet can reach zero. Likewise, if every element is positive, the smallest sum exceeds zero. The early-exit check if (nums[i] > 0) break handles the all-positive case in O(1) after sorting.
class Solution { public List<List<Integer>> threeSum(int[] nums) { // Step 1: Sort — enables two-pointer and duplicate skipping Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length - 2; i++) { // Skip duplicate fixed elements if (i > 0 && nums[i] == nums[i - 1]) continue; // Early exit: if nums[i] > 0, no solution possible if (nums[i] > 0) break; int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { // Found a valid triplet! result.add(Arrays.asList(nums[i], nums[left], nums[right])); // Skip duplicates on the left while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates on the right while (left < right && nums[right] == nums[right - 1]) right--; // Move both inward to search for more triplets left++; right--; } else if (sum < 0) { left++; // Need a larger sum → move left right } else { right--; // Need a smaller sum → move right left } } } return result; } }
func threeSum(nums []int) [][]int { // Step 1: Sort — enables two-pointer and duplicate skipping sort.Ints(nums) result := [][]int{} for i := 0; i < len(nums)-2; i++ { // Skip duplicate fixed elements if i > 0 && nums[i] == nums[i-1] { continue } // Early exit: if nums[i] > 0, no solution possible if nums[i] > 0 { break } left, right := i+1, len(nums)-1 for left < right { sum := nums[i] + nums[left] + nums[right] if sum == 0 { // Found a valid triplet! result = append(result, []int{nums[i], nums[left], nums[right]}) // Skip duplicates on the left for left < right && nums[left] == nums[left+1] { left++ } // Skip duplicates on the right for left < right && nums[right] == nums[right-1] { right-- } // Move both inward to search for more triplets left++ right-- } else if sum < 0 { left++ // Need a larger sum → move left right } else { right-- // Need a smaller sum → move right left } } } return result }
def three_sum(nums: list[int]) -> list[list[int]]: # Step 1: Sort — enables two-pointer and duplicate skipping nums.sort() result: list[list[int]] = [] for i in range(len(nums) - 2): # Skip duplicate fixed elements if i > 0 and nums[i] == nums[i - 1]: continue # Early exit: if nums[i] > 0, no solution possible if nums[i] > 0: break left, right = i + 1, len(nums) - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total == 0: # Found a valid triplet! result.append([nums[i], nums[left], nums[right]]) # Skip duplicates on the left while left < right and nums[left] == nums[left + 1]: left += 1 # Skip duplicates on the right while left < right and nums[right] == nums[right - 1]: right -= 1 # Move both inward to search for more triplets left += 1 right -= 1 elif total < 0: left += 1 # Need a larger sum → move left right else: right -= 1 # Need a smaller sum → move right left return result
impl Solution { pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> { // Step 1: Sort — enables two-pointer and duplicate skipping let mut nums = nums; nums.sort(); let mut result: Vec<Vec<i32>> = Vec::new(); let n = nums.len(); for i in 0..n.saturating_sub(2) { // Skip duplicate fixed elements if i > 0 && nums[i] == nums[i - 1] { continue; } // Early exit: if nums[i] > 0, no solution possible if nums[i] > 0 { break; } let (mut left, mut right) = (i + 1, n - 1); while left < right { let sum = nums[i] + nums[left] + nums[right]; if sum == 0 { // Found a valid triplet! result.push(vec![nums[i], nums[left], nums[right]]); // Skip duplicates on the left while left < right && nums[left] == nums[left + 1] { left += 1; } // Skip duplicates on the right while left < right && nums[right] == nums[right - 1] { right -= 1; } // Move both inward to search for more triplets left += 1; right -= 1; } else if sum < 0 { left += 1; // Need a larger sum → move left right } else { right -= 1; // Need a smaller sum → move right left } } } result } }
function threeSum(nums: number[]): number[][] { // Step 1: Sort — enables two-pointer and duplicate skipping nums.sort((a, b) => a - b); const result: number[][] = []; for (let i = 0; i < nums.length - 2; i++) { // Skip duplicate fixed elements if (i > 0 && nums[i] === nums[i - 1]) continue; // Early exit: if nums[i] > 0, no solution possible if (nums[i] > 0) break; let left = i + 1, right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { // Found a valid triplet! result.push([nums[i], nums[left], nums[right]]); // Skip duplicates on the left while (left < right && nums[left] === nums[left + 1]) left++; // Skip duplicates on the right while (left < right && nums[right] === nums[right - 1]) right--; // Move both inward to search for more triplets left++; right--; } else if (sum < 0) { left++; // Need a larger sum → move left right } else { right--; // Need a smaller sum → move right left } } } return result; }
Enter an array and watch the two-pointer algorithm find all triplets step by step.
Sorting costs O(n log n), but the dominant term is the outer loop O(n) multiplied by the inner two-pointer scan O(n), giving O(n2) total. Space is O(1) excluding the output list — the sort is in-place and we only use a few pointer variables.
Three nested loops each iterate up to n elements, checking every possible triplet. The total number of combinations is n*(n-1)*(n-2)/6, which simplifies to O(n3). Only a few index variables are needed, so space is constant.
The outer loop fixes one element in O(n), and for each fixed element the two-pointer scan covers the remaining subarray in O(n). Sorting costs O(n log n) but is dominated by the O(n) x O(n) = O(n2) main phase. The in-place sort and pointer variables use O(1) auxiliary space.
Sorting is the key enabler. It lets us skip duplicates with a simple neighbor comparison and powers the two-pointer inner loop, reducing the cubic brute force down to quadratic. This is provably optimal — 3Sum has a lower bound of Ω(n2) in the comparison-based model.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.