3sum Solution for Amazon
Company: Amazon · Difficulty: Hard · Topics: Array, Two Pointers, Sorting
Problem Statement
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.
Examples
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: The triplets that sum to zero are [-1,-1,2] and [-1,0,1].
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: No triplet sums to zero.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only triplet that sums to zero is [0,0,0].
Example 4:
Input: nums = [-2,0,1,1,2]
Output: [[-2,0,2],[-2,1,1]]
Explanation: The triplets that sum to zero are [-2,0,2] and [-2,1,1].
Intuition
The key insight is to use a two-pointer approach after sorting the array. For each element, we use two pointers to find pairs that sum to the negative of the current element.
Approach
Approach 1: Two Pointers with Sorting (Optimal)
1. Sort the array
2. For each element nums[i], use two pointers (left and right) to find pairs
3. Skip duplicates to avoid duplicate triplets
4. If sum == 0, add triplet to result
Approach 2: Two Pointers with Early Termination
1. Same as two pointers but with additional optimizations
2. Skip elements that are too large (nums[i] > 0)
3. Skip duplicate elements efficiently
Approach 3: Brute Force
1. Use three nested loops
2. Check all possible triplets
3. Avoid duplicates using hash set
Dry Run
Let's trace through Example 1: nums = [-1,0,1,2,-1,-4]
After sorting: [-4,-1,-1,0,1,2]
Two Pointers Approach:
- i=0, nums[i]=-4: left=1, right=5, sum=-4+(-1)+2=-3 < 0, left++
- i=0, nums[i]=-4: left=2, right=5, sum=-4+(-1)+2=-3 < 0, left++
- i=0, nums[i]=-4: left=3, right=5, sum=-4+0+2=-2 < 0, left++
- i=0, nums[i]=-4: left=4, right=5, sum=-4+1+2=-1 < 0, left++
- i=0, nums[i]=-4: left=5, right=5, break (left >= right)
- i=1, nums[i]=-1: left=2, right=5, sum=-1+(-1)+2=0, add [-1,-1,2], left++, right--
- i=1, nums[i]=-1: left=3, right=4, sum=-1+0+1=0, add [-1,0,1], left++, right--
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Two Pointers with Sorting (Optimal)
Time Complexity: O(n²) - We traverse the array once for each element
Space Complexity: O(1) - Only need a few variables
Solution 2: Two Pointers with Optimizations
Time Complexity: O(n²) - We traverse the array once for each element
Space Complexity: O(1) - Only need a few variables
Solution 3: Brute Force
Time Complexity: O(n³) - Three nested loops
Space Complexity: O(n) - Hash set for duplicates