3Sum
Return all unique triplets in nums that sum to zero. Triplets must be unique up to ordering.
Answers use simple, clear English.
Audio N/AQuick interview answer
Sort, then for each i run two pointers on the right side. Skip duplicate values for i, lo, and hi to avoid repeat triplets. O(n²) time after O(n log n) sort.
Detailed answer
Sort, then for each i run two pointers on the right side. Skip duplicate values for i, lo, and hi to avoid repeat triplets. O(n²) time after O(n log n) sort. Hash-set based variants exist but sorting + two pointers is the clean interview solution.
Full explanation
Hash-set based variants exist but sorting + two pointers is the clean interview solution.
Real example & use case
Balancing three ledger entries that must net to zero in a reconciliation tool.
Pros & cons
Pros: deterministic uniqueness via sorting. Cons: O(n²); careful duplicate skipping.
Code example
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
res: list[list[int]] = []
n = len(nums)
for i in range(n):
if i and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return resPractice code · python (view only · no execution)
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
res: list[list[int]] = []
n = len(nums)
for i in range(n):
if i and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi + 1]:
hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return res