The three-sum problem requires finding all unique triplets in an array that add up to zero. While depth-first search can solve this after sorting, a more efficient approach uses the two-pointer technique on a sorted array.

Key Points

• Use two pointers, not a single pointer—common mistake to avoid
• Recommended solving time: 20 minutes

Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the triplets must not contain duplicate combinations.

Approach Analysis

Two main methods exist for solving this problem.

Approach One: DFS with Pruning

A naive DFS approach would have O(C(n,3)) complexity, which is too slow. However, since the target sum is known (zero), we can prune branches that cannot possibly lead to valid solutions by utilizing the sorted nature of the array. The sum behavior in sorted sequences follows predictable patterns, allowing early termination of invalid paths.

Approach Two: Two-Pointer Technique

This approach requires fixing one element and then using two pointers to find complementary pairs. The key insight is: after sorting, if we fix nums[i], then for any valid pair nums[j] and nums[k], increasing j will require decreasing k to maintain the sum property.

Common Mistake: Many implementations incorrectly use a single pointer by fixing both ends and searching between them. This fails on cases like [-2, 0, 1, 1, 2] because it becomes unclear which pointer to move when the sum doesn't equal zero.

The correct approach: Fix one element, then use two pointers in the remaining sorted subarray to find valid pairs.

Implementation

Here is a clean two-pointer implementation:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        
        for idx in range(len(nums)):
            if idx > 0 and nums[idx] == nums[idx - 1]:
                continue
            
            target = -nums[idx]
            right = len(nums) - 1
            
            for left in range(idx + 1, len(nums) - 1):
                if left != idx + 1 and nums[left] == nums[left - 1]:
                    continue
                
                while left < right and nums[left] + nums[right] > target:
                    right -= 1
                
                if left < right and nums[left] + nums[right] == target:
                    result.append([nums[idx], nums[left], nums[right]])
        
        return result

The algorithm works as follows:

1. Sort the array first
2. Iterate through each element as the fixed number
3. Skip duplicate values at each level to avoid duplicate triplets
4. Use two pointers (left and right) to find pairs that sum to the negative of the fixed element
5. Move pointers strategically based on whether the current sum is greater or less than target

Another equivalent implementation:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        
        for i in range(len(nums)):
            left, right = i + 1, len(nums) - 1
            
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                
                if current_sum == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    while left < right and nums[right - 1] == nums[right]:
                        right -= 1
                    right -= 1
                    
                    while left < right and nums[left + 1] == nums[left]:
                        left += 1
                    left += 1
                elif current_sum < 0:
                    left += 1
                else:
                    right -= 1
        
        return result

Critical Considerations

When implementing, ensure duplicate skipping occurs at all three levels: the outer loop, the inner loop, and after finding a valid triplet. This prevents duplicate results from appearing in the output.

Time Complexity: O(n²) after sorting Space Complexity: O(1) excluding the output space