Asteroid collision
Rocks drift in a row through space, listed from left to right in asteroids. Each number is one rock. The number without its sign is the rock's size, and the sign is its direction: a positive rock flies right (a right-flier) and a negative rock flies left (a left-flier). Every rock flies at the same speed, so rocks heading the same way keep their gaps and never touch.
When a right-flier and a left-flier meet head on, the smaller one breaks up and is gone, and the bigger one keeps going. A tie breaks both. A left-flier that starts to the left of a right-flier never meets it, because they fly apart.
Return the rocks still flying after every crash has happened, as a list in their original left-to-right order. If none are left, return an empty list.
asteroids = [3, 9, -4]Output[3, 9]The -4 flies left into the 9. The 9 is bigger, so the -4 breaks. The 3 and the 9 fly the same way and never meet.
asteroids = [6, -6, 2]Output[2]The 6 and the -6 are the same size, so both break. The 2 flies right, away from everything.
asteroids = [2, 5, -8, 4]Output[-8, 4]The -8 breaks the 5, then the 2, and keeps flying left. The 4 flies right, away from the -8.
asteroids = [-3, -1, 2, 7]Output[-3, -1, 2, 7]Every left-flier starts to the left of every right-flier, so no two rocks ever meet.
1 ≤ len(asteroids) ≤ 105
Every item is a nonzero integer from -1,000 to 1,000.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.