15. 3Sum
Asked at Google, Meta, Amazon, Apple and 5 more
Difficulty
Medium
Time
O(n^2)
Space
O(1)
Pattern
Array
Companies
9
Problem
You are given an integer array nums. Find every group of three different positions i, j, k where the three values add up to zero: nums[i] + nums[j] + nums[k] == 0.
Return a list of those triplets. The same triplet must appear only once in the answer, even if the array contains the same numbers in several places. For example, if the array has two -1 values, the triplet [-1, 0, 1] should still be listed once.
The order of the triplets in your answer does not matter, and the order of the three numbers inside a triplet does not matter either.
Find groups of three that add to zero
Constraints
- ●
3 <= nums.length <= 3000 - ●
-10^5 <= nums[i] <= 10^5
Examples
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]nums = [0,1,1][]nums = [0,0,0][[0,0,0]]Asked At
9 companies| 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 → |
| Bloomberg | Medium | View all Bloomberg 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.
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.
Fix one value, then use two pointers
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
O(n^2) timedef 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 runs in O(n^2) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask 3Sum?
3Sum is asked at Google, Meta, Amazon, Apple, Microsoft, Oracle, Salesforce, Walmart, Bloomberg. 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.