LeetCode 15: 3Sum

Problem 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.

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
-10⁵ <= nums[i] <= 10⁵

Difficulty: Medium

Tags: array, two pointers, sorting

Rating: 91.42%

Solution Approach

Let’s break down the solution step by step, understanding each optimization and technique used.

Key Insights

Sorting First:
- By sorting the array first, we can:
  - Easily skip duplicates
  - Use the two-pointer technique
  - Enable early termination optimizations
Early Termination:
- If the smallest three numbers sum to > 0, we can stop
- If the largest three numbers sum to < 0, we can skip the current number
- If all positive or all negative numbers, return empty result
Two-Pointer Technique:
- After fixing one number, use two pointers to find the other two numbers
- Move pointers based on sum comparison with target

Implementation

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # Edge case handling
        if len(nums) < 3: 
            return []
            
        # Sort array for two-pointer technique
        nums.sort()
        n = len(nums)
        result = []
        
        # Early termination if all positive or all negative
        if nums[0] > 0 or nums[-1] < 0: 
            return []
            
        # Fix first number and use two pointers for other two
        for i in range(n-2):
            # Skip duplicates for first number
            if i > 0 and nums[i] == nums[i-1]: 
                continue
                
            # Early termination optimizations
            if nums[i] + nums[i+1] + nums[i+2] > 0: 
                break  # smallest possible sum > 0
            if nums[i] + nums[n-2] + nums[n-1] < 0: 
                continue  # largest possible sum < 0
                
            left = i + 1
            right = n - 1
            target = -nums[i]
            
            while left < right:
                current_sum = nums[left] + nums[right]
                
                if current_sum == target:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # Skip duplicates for both pointers
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]: 
                        left += 1
                    while left < right and nums[right] == nums[right+1]: 
                        right -= 1
                        
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1
                    
        return result

Complexity Analysis

Time Complexity: $O(n²)$

Sorting: O(n log n)
Main loop: O(n)
- Two-pointer technique for each iteration: O(n)
Overall: O(n²) as the nested loop dominates

Space Complexity: $O(1)$ or $O(n)$

O(1) extra space excluding the output array
O(n) if we count the space used to store the result
The sorting algorithm might use additional space depending on the implementation

Optimization Techniques

Early Termination
```
if nums[0] > 0 or nums[-1] < 0: 
    return []
```
This simple check avoids processing arrays that can’t possibly have a solution.
Skip Duplicates
```
if i > 0 and nums[i] == nums[i-1]: 
    continue
```
Skipping duplicates early prevents generating duplicate triplets.

Range Check

if nums[i] + nums[i+1] + nums[i+2] > 0: break
if nums[i] + nums[n-2] + nums[n-1] < 0: continue

These checks quickly eliminate ranges that can’t contain valid triplets.