Resolve colliding buy and sell sweeps

Question

Model each sweep as a signed integer: positive means moving right, negative means moving left, and the magnitude is its size. All sweeps move at the same speed. When a right-mover meets a left-mover, the smaller one is destroyed; if equal, both are destroyed. Same-direction sweeps never collide. Return the surviving sweeps in order.

[5, 10, -5]  -> [5, 10]     # -5 hits 10 and loses
[8, -8]      -> []          # equal magnitudes annihilate
[-2, -1, 1, 2] -> [-2, -1, 1, 2]   # left-movers on the left never meet right-movers

Return the list of surviving sweeps.

Accepted Answer

Process sweeps left to right using a stack of survivors. A collision only happens when the incoming sweep moves left (< 0) and the stack top moves right ( 0). Resolve repeatedly: if the top is smaller it is popped (and the incoming sweep may collide again); if equal, both vanish; if the top is larger, the incoming sweep dies. A sweep that survives all collisions is pushed. Tracing [5, 10, -5]: -5 meets 10, loses, and is discarded, leaving [5, 10]. Time O(n) (each sweep pushed and popped at most once), space O(n). Edge cases: two left-movers or two right-movers in a row never collide; equal ma…

Resolve colliding buy and sell sweeps

Your answer

More Coding questions