Nail the duplicate skips without a hint
Three weeks from now, they're the part you'll blank on. Write 3Sum yourself in the 14-day free trial, and the learning engine brings it back before you forget it.
The problem
You are given an array of integers nums. Return every triplet of values that adds up to zero, where the three values come from three different indices of nums. Return each triplet only once, even when a value appears at several indices and the triplet can be made more than one way. If no triplet adds up to zero, return an empty list.
The order of the result is checked. Write the three values of each triplet from smallest to largest, and list the triplets in ascending order: by first value, and by second value when the first values are equal.
Constraints
- 3 <=
nums.length<= 3000 - -10^5 <=
nums[i]<= 10^5
Example
- Input
nums = [3, -2, 1, 0, -1, 2, -1]- Output
[[-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]]
-1 appears twice, so [-2, -1, 3] and [-1, 0, 1] can each be built two ways, but each goes in the answer once.
How to solve it
Three nested loops check every group of three. That's O(n³), about 4.5 billion groups at the limit of 3,000 numbers, and you'd still need a set to drop the copies. Name it and its cost, then move to the faster idea.
Fix one number and the problem shrinks. If the first number is -2, the other two have to add up to 2, and that's Two Sum. So sort the array first. Then fix each number in turn and run two pointers on the numbers to its right: left just after it, right at the end. If the total is below zero, move left up to a bigger number. If it's above zero, move right down. If it's zero, record the triplet and move both.
Sorting is allowed here because you return values, not indices, and it lines copies up side by side. That gives you the two places to skip duplicates: when the next number to fix equals the one before it, skip it, because its triplets are already found; and after a match, move the pointers past copies of the values they just used.
3Sum([-2,-2,0,1,1,2])
The run starts on [-2,-2,0,1,1,2].
The pointers never jump over a triplet. When the total is too small, even the biggest remaining number can't rescue the number at left, so dropping it loses nothing. When it's too big, the number at right is too big even for the smallest remaining partner. Every triplet gets found, and the skips only pass over copies of ones already recorded.
This sorts the input in place, so sort a copy if the caller needs the original order. And if they ask for something faster, there's no known way to beat O(n²) by more than a log factor.
Python solution
from typing import List
class Solution:
def three_sum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return resultTime and space complexity
- Time O(n²)
- Sorting is O(n log n), then each fixed number gets one sweep of the two pointers.
- Space O(n)
- The sort can use up to O(n) extra space depending on the language. Beyond the output, the pointers need O(1).