Three positions that net to flat

Question

Given signed position sizes (longs positive, shorts negative), find all unique triples that net to exactly zero, three positions that together leave you flat. Triples that are reorderings of each other count once.

positions = [-2, -1, 0, 1, 2]
-> [[-2, 0, 2], [-1, 0, 1]]

Return all unique zero-sum triples. Aim for $O(n^2)$ .

Accepted Answer

Sort the array. Fix each value as the smallest of a triple, then two-pointer the remainder for a pair summing to its negation. Skip duplicate values at the fixed position and after each match to avoid repeated triples, since equal values would otherwise regenerate the same triple. Tracing [-2, -1, 0, 1, 2]: fixing -2 finds 0 + 2; fixing -1 finds 0 + 1; other fixed values yield nothing new. The result is [[-2, 0, 2], [-1, 0, 1]]. Time O(n^2), an outer loop over the fixed value and an inner linear two-pointer, space O(1) beyond the output. The duplicate-skipping at all three positions is what g…

Three positions that net to flat

Your answer

More Coding questions