3Sum
Asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Salesforce, Walmart
Problem
Given an array of integers, find all unique triplets that sum to zero. This problem extends Two Sum into three dimensions and tests your ability to handle duplicates and optimize with two pointers.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: three nested loops checking every triplet. That's O(n³) — n³/6 triplets to check. Way too slow.
Key insight: sort the array first. Then for each element nums[i], use two pointers (left and right) to find pairs that sum to -nums[i]. This reduces the inner search from O(n²) to O(n).
Why sorting helps: with a sorted array, if the sum is too small, move left right (increases sum). If too large, move right left (decreases sum). This eliminates half the search space at each step.
The main pitfall is duplicates. You must skip duplicate values at three places: (1) skip duplicate nums[i] values, (2) skip duplicate left values after finding a triplet, (3) skip duplicate right values after finding a triplet.
Visual walkthrough for [-1, 0, 1, 2, -1, -4]:
Sort: [-4, -1, -1, 0, 1, 2]
- i=0, nums[i]=-4. Target sum=4. left=1, right=5.
-1+2=1 < 4, move left. -1+2=1 < 4, move left. 0+2=2 < 4, move left. 1+2=3 < 4, left meets right. No triplet.
- i=1, nums[i]=-1. Target sum=1. left=2, right=5.
-1+2=1 == 1! Triplet [-1,-1,2]. Skip duplicates. left=4, right=4. Stop.
- i=2, nums[i]=-1. Same as i=1. Skip (duplicate).
- i=3, nums[i]=0. Target sum=0. left=4, right=5.
1+2=3 > 0, move right. left meets right. No triplet.
Result: [[-1,-1,2], [-1,0,1]]
Edge cases: fewer than 3 elements (return empty), all zeros (return one triplet [0,0,0]), no valid triplets (return empty).
Optimal Approach
Step 1: Sort the array.
Step 2: For each index i (skip duplicates):
- Set left = i+1, right = n-1
- Calculate sum = nums[i] + nums[left] + nums[right]
- If sum == 0: record triplet, skip duplicates on both sides, move both pointers
- If sum < 0: move left right (need larger sum)
- If sum > 0: move right left (need smaller sum)
The duplicate skip at nums[i] is critical. Without it, you'd record the same triplet multiple times.
Time: O(n²) — outer loop O(n), inner two-pointer scan O(n). Space: O(1) excluding output.
What Trips People Up in Real Interviews
Forgetting to sort first. Without sorting, you can't use the two-pointer technique. Sorting is O(n log n) and is the prerequisite for the O(n²) solution.
Skipping duplicate elements incorrectly. After finding a valid triplet, skip all duplicate values to avoid duplicate triplets. But don't skip the first occurrence — you need it.
Confusing "return all unique triplets" with "return all triplets." If the input has duplicates like [-1, -1, 2], you should only return [-1, -1, 2] once, not twice.
Not handling the case where no triplet exists. Return an empty list, not null or an error.
Off-by-one in the outer loop: using range(len(nums)) instead of range(len(nums) - 2). The last two elements can't be the first element of a triplet since you need at least two elements after them.
Solution Code
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
return resultFrequently Asked Questions
What is the 3Sum problem?
Given an array of integers, find all unique triplets that sum to zero. This problem extends Two Sum into three dimensions and tests your ability to handle duplicates and optimize with two pointers.
How do you solve 3Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask 3Sum?
3Sum is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on 3Sum?
- Forgetting to sort first. Without sorting, you can't use the two-pointer technique. Sorting is `O(n log n)` and is the prerequisite for the `O(n²)` solution.
- Skipping duplicate elements incorrectly. After finding a valid triplet, skip all duplicate values to avoid duplicate triplets. But don't skip the first occurrence — you need it.
- Confusing "return all unique triplets" with "return all triplets." If the input has duplicates like [-1, -1, 2], you should only return [-1, -1, 2] once, not twice.
- Not handling the case where no triplet exists. Return an empty list, not `null` or an error.
- Off-by-one in the outer loop: using range(len(nums)) instead of range(len(nums) - 2). The last two elements can't be the first element of a triplet since you need at least two elements after them.