MediumNeetCode150ArrayTwo PointersSorting
3Sum
Return all unique triplets that sum to zero.
Examples
Input
nums = [-1,0,1,2,-1,-4]
Output
[[-1,-1,2],[-1,0,1]]
Distinct triplets summing to zero.
Constraints
- •
3<=nums.length<=3000 - •
-10^5<=nums[i]<=10^5
Approaches
Check all triplets.
CodeT: O(n^3) | S: O(1)
def threeSum(nums):
r=[]; nums.sort()
for i in range(len(nums)-2):
for j in range(i+1,len(nums)-1):
for k in range(j+1,len(nums)):
if nums[i]+nums[j]+nums[k]==0:
t=[nums[i],nums[j],nums[k]]
if t not in r: r.append(t)
return rSort then two pointers.
CodeT: O(n^2) | S: O(1)
def threeSum(nums):
r=[]; nums.sort()
for i in range(len(nums)-2):
if i>0 and nums[i]==nums[i-1]: continue
l,r_=i+1,len(nums)-1
while l<r_:
t=nums[i]+nums[l]+nums[r_]
if t==0:
r.append([nums[i],nums[l],nums[r_]])
while l<r_ and nums[l]==nums[l+1]: l+=1
while l<r_ and nums[r_]==nums[r_-1]: r_-=1
l+=1; r_-=1
elif t<0: l+=1
else: r_-=1
return rSame as optimized.
Diagram
nums=[-4,-1,-1,0,1,2], skip dup, two pointers
CodeT: O(n^2) | S: O(1)
def threeSum(nums):
res=[]; nums.sort()
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]: continue
l,r_=i+1,len(nums)-1
while l<r_:
t=nums[i]+nums[l]+nums[r_]
if t<0: l+=1
elif t>0: r_-=1
else:
res.append([nums[i],nums[l],nums[r_]])
while l<r_ and nums[l]==nums[l+1]: l+=1
while l<r_ and nums[r_]==nums[r_-1]: r_-=1
l+=1; r_-=1
return resComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^3) | O(1) | Check all triplets. |
| Two Pointers | O(n^2) | O(1) | Sort then two pointers. |
| Two Pointers with Dedup | O(n^2) | O(1) | Same as optimized. |
Brute Force
T: O(n^3)S: O(1)
Check all triplets.
Two Pointers
T: O(n^2)S: O(1)
Sort then two pointers.
Two Pointers with Dedup
T: O(n^2)S: O(1)
Same as optimized.
Common Mistakes
Not skipping first element duplicates
Not moving both pointers after match
Forgetting to sort