A complete visual walkthrough of the sort + two pointer approach — from brute force to optimal O(n²) with duplicate handling.
The 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 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.
Make sure your solution handles these correctly:
i < n-2 handles this.Early exit optimization: If after sorting, nums[i] > 0, we can break the outer loop. All remaining elements are positive, so no three positive numbers can sum to zero.
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; } }
Enter an array and watch the two-pointer algorithm find all triplets step by step.
Total: O(n log n) + O(n) × O(n) = O(n²).
Space is O(1) excluding the output list. The sort is in-place and we only use a few pointer variables. Some implementations of sorting use O(log n) stack space, but the algorithm itself requires no auxiliary data structures.
Can we beat O(n²)? No. It's been proven that 3Sum has a lower bound of Omega(n²) in the comparison-based model. Our solution is asymptotically optimal.