Three Values Summing to Zero
Problem
A ledger audit looks for three entries that cancel out exactly. Given a list of integers nums, return every distinct triplet [a, b, c] of values taken from three different positions with a + b + c = 0. Write each triplet in ascending order and list the triplets in ascending order; two triplets with the same values count once. The list has up to 3,000 values, so trying every triple is too slow.
Examples
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Why: the two -1 values can both be used, but [-1, 0, 1] is listed onceInput: nums = [0, 1, 1]
Output: []Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
Why: edge case, four zeros still give just one distinct tripletHints
0 / 3
Fix the smallest value a. What is left is a two-value problem: find b + c = -a in the rest of the list.
On a sorted list, two pointers solve the two-value part in one pass: if the sum is too small move the left pointer right, if too big move the right pointer left.
Sort first. Skip an a equal to the previous a, and after recording a triplet move the left pointer past any repeats of its value. That removes duplicates without a set.
Solution
After sorting, fixing the first value a turns the rest into a pair search for -a on the part of the list to its right, and two pointers from both ends find every pair in one pass because moving the left pointer only raises the sum and moving the right one only lowers it. Duplicates are skipped at both levels: a value of a equal to the one before it would repeat the same triplets, and after a match the left pointer steps past equal values, since once a and b are fixed the third value is fixed too. Once a is positive no triplet can sum to zero, so the loop stops early. Time is O(n²), and extra space is O(n) for the sorted copy.
def zero_triplets(nums):
s, out = sorted(nums), []
for i in range(len(s) - 2):
if s[i] > 0:
break # three positives never sum to zero
if i > 0 and s[i] == s[i - 1]:
continue # same first value, same triplets
lo, hi = i + 1, len(s) - 1
while lo < hi:
total = s[i] + s[lo] + s[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
out.append([s[i], s[lo], s[hi]])
lo += 1
hi -= 1
while lo < hi and s[lo] == s[lo - 1]:
lo += 1 # skip repeats of the middle value
return out
print(zero_triplets([-1, 0, 1, 2, -1, -4])) # -> [[-1, -1, 2], [-1, 0, 1]]
print(zero_triplets([0, 1, 1])) # -> []
print(zero_triplets([0, 0, 0, 0])) # -> [[0, 0, 0]]Stuck on the idea rather than the code? Two Pointers covers it.