Particles sit in a row on a straight track. Each is described by a non-zero integer: its absolute value is the particle's mass, and its sign is its direction (positive moves right, negative moves left). All particles move at the same speed.
When a right-mover meets a left-mover, the lighter one is destroyed; if their masses are equal, both are destroyed. The survivor keeps going in its direction and may hit more particles. Two particles moving the same way never meet, and neither do a left-mover that is to the left of a right-mover.
Write after_collisions(particles) that returns the particles left once no more collisions can happen, in their original left-to-right order.
after_collisions([4, 9, -6]) # [4, 9] (-6 hits 9 and is destroyed)
after_collisions([7, -7]) # [] (equal masses: both go)
after_collisions([2, 3, -5, 1]) # [-5, 1] (-5 destroys 3, then 2)
after_collisions([-3, -1, 2, 5]) # [-3, -1, 2, 5] (nobody meets)
Constraints: 1 <= len(particles) <= 2 * 10^5; each value is non-zero and in [-10^6, 10^6].
Simulating round by round, or rescanning the row after every collision, is O(n²). Aim for O(n).
Show hint
scan left to right. A new left-mover can only collide with right-movers that are still standing, and it meets the nearest one first.