Hull trim

Three lead slugs have to cancel exactly. The triple loop is billions of combinations, and it reports the same trio over and over.

The problem

A boatyard trims a small racing hull with stamped lead slugs. Each slug carries a signed gram value: a positive stamp shifts weight toward the bow, a negative one toward the stern, and a slug stamped 0 is a spacer. The hull sits level when the stamps of the fitted slugs add to zero, and the class rules allow exactly three slugs.

The yard wants every distinct trim that levels the hull. Two trims count as the same if they use the same three stamped values in any order — the box holds many slugs stamped alike, and nobody cares which physical slug a rigger grabs.

Input. slugs — a list of integers, the stamped gram values in the box, in no particular order.

Output. Every distinct trio of stamped values summing to zero. Each trio is a list of three values, and two trios with the same three values are one trio.

Example.

slugs = [-4, -1, -1, 0, 1, 2, 5]   ->  [[-4, -1, 5], [-1, -1, 2], [-1, 0, 1]]

Three trims level the hull. [-1, -1, 2] uses two slugs stamped -1, legal because the box holds two of them, while [-1, 0, 1] uses the -1 once.

A second example, where duplicates must not multiply the answer:

slugs = [0, 0, 0, 0]   ->  [[0, 0, 0]]
slugs = [3, 3, 3]      ->  []

Four spacers give one trim, not the four the combinations suggest. Three slugs stamped 3 cannot cancel.

Constraints.

• 0 <= len(slugs) <= 3000
• -10^5 <= slugs[i] <= 10^5
• The order of the trios in the output does not matter.

Hints

Approach

Brute force

Three nested loops over the box: about 4.5 billion triples for 3000 slugs. It also leaves the harder half of the job, since the raw output repeats [0, 0, 0] four times for a box of four spacers.

The insight

Sort the box first; then fixing the lightest slug of a trio turns the rest into a two-sum on a sorted list, and two pointers close that in one pass.

Hold slugs[i] as the anchor and look for two later values summing to -slugs[i], with lo just after the anchor and hi at the end. If the three add to less than zero the only repair is a larger low value, so lo moves up; if they add to more, hi moves down. Neither pointer ever reverses, so the pair is found or ruled out in one sweep.

Sorting pays twice: equal stamps become neighbours, so skipping a repeated anchor is one comparison and skipping a run after a hit is a short slide. Deduplication stops being a separate phase.

Algorithm

1. Sort slugs ascending.
2. For each index i from 0 to n - 3:
3. If i > 0 and slugs[i] == slugs[i - 1], skip — that anchor is done.
4. If slugs[i] > 0, stop: the anchor is the smallest of its trio, so the sum cannot reach zero.
5. Set lo = i + 1, hi = n - 1. While lo < hi, take the three-way sum: if negative raise lo, if positive lower hi.
6. On zero, record the trio, then slide both pointers past their runs of equal values.

Complexity

Time O(n²) — an n log n sort, then n anchors each running a linear sweep: about 4.5 million steps at the maximum size, not 4.5 billion. Space O(1) beyond the sorted list and the output.

Solution

"""Hull trim — sort the slugs, fix an anchor, close the pair with two pointers."""


def solve(slugs):
    stamps = sorted(slugs)
    n = len(stamps)
    trims = []
    for i in range(n - 2):
        # The anchor is the smallest stamp of its trio, so once it turns
        # positive the other two are at least as large and nothing can reach 0.
        if stamps[i] > 0:
            break
        if i > 0 and stamps[i] == stamps[i - 1]:
            continue                       # this anchor's trios are already out
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = stamps[i] + stamps[lo] + stamps[hi]
            if total < 0:
                lo += 1                    # only a larger low stamp can lift it
            elif total > 0:
                hi -= 1                    # only a smaller high stamp can drop it
            else:
                trims.append([stamps[i], stamps[lo], stamps[hi]])
                lo += 1
                hi -= 1
                # Slide past runs of equal stamps so the trio is emitted once.
                while lo < hi and stamps[lo] == stamps[lo - 1]:
                    lo += 1
                while lo < hi and stamps[hi] == stamps[hi + 1]:
                    hi -= 1
    return trims

TESTS = [
    (([-4, -1, -1, 0, 1, 2, 5],), [[-4, -1, 5], [-1, -1, 2], [-1, 0, 1]]),
    (([0, 0, 0, 0],), [[0, 0, 0]]),
    (([3, 3, 3],), []),
    (([],), []),
    (([-2, 0, 0, 2, 2],), [[-2, 0, 2]]),
    (([1, -1],), []),
    (([-100000, 50000, 50000, 1],), [[-100000, 50000, 50000]]),
]

Pitfalls

• Skipping a repeated anchor by comparing forward. Testing slugs[i] == slugs[i + 1] and skipping deletes exactly the trios that legitimately use two equal slugs: [-1, -1, 2] vanishes from the first example. Compare backward, against slugs[i - 1].
• Advancing one step after a hit. lo += 1; hi -= 1 alone re-emits a trio when equal values sit side by side — on [-2, 0, 0, 2, 2] the trim [-2, 0, 2] comes out twice.
• Collapsing duplicates with a set at the end. It gives the right list and hides the mistake, at the cost of an extra pass and memory for repeats the skips would have prevented.

Variants

• Crate digging — the same "sort, then let the order prune" move, over two lists instead of one.
• Micron drift — pointers closing inward on a list that is sorted for you already.