3Sum
You get a list of integers. Return every group of three numbers from the list that adds up to 0. Each group must use three different positions of the list.
The result must not contain the same group twice, even if the list contains repeated values. The groups can be returned in any order, and the numbers inside a group can be in any order.
Examples
Input nums = [-1, 0, 1, 2, -1, -4]
Output [[-1, -1, 2], [-1, 0, 1]]
Input nums = [0, 1, 1]
Output []
No group adds up to 0.
Input nums = [0, 0, 0]
Output [[0, 0, 0]]
Constraints
- 3 <= nums.length <= 3,000
- -100,000 <= nums[i] <= 100,000
Stuck? Take one hint at a time
Common mistakes
- Forgetting to skip repeated first numbers, which duplicates triples.
- Skipping repeated left or right values before recording a triple, which can miss a valid one such as [0, 0, 0].
- Returning the triples in a list of sets and then comparing them incorrectly.
- Using the same position twice in a triple.
Questions an interviewer may ask next
- Find the triple whose sum is closest to a target. (The same sweep, tracking the best gap.)
- Four numbers that add up to a target (4Sum). How does the cost grow?
- Count the triples instead of listing them.
- Solve it without sorting, using a hash set. What new problems does that create with duplicates?
How often this is reported
Commonly reported across 14 of 25 tracked companies
14/25
Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.
nums
[-1,0,1,2,-1,-4]
Expected output
[[-1,-1,2],[-1,0,1]]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.