Asteroid Collision

Problem

You are given an integer array asteroids. Each element describes one asteroid on a straight line: its absolute value is the asteroid's size, and its sign is its direction (positive moves right, negative moves left). All asteroids move at the same speed.

When two asteroids meet, the smaller one is destroyed; if they are the same size, both are destroyed. Two asteroids moving in the same direction never meet. Return the array of asteroids that survive after all collisions, in their original order.

• There are between 2 and 20,000 asteroids.
• Each size is between 1 and 5,000 in absolute value; no element is 0.

Examples

• asteroids = [4, 12, -6] → [4, 12]. The 12 and -6 collide and 12 survives; 4 and 12 move the same way and never meet.
• asteroids = [7, -7] → []. Equal sizes annihilate each other.
• asteroids = [15, 3, -9] → [15]. The -9 first destroys 3, then hits 15 and is destroyed.
• asteroids = [-3, -1, 2, 6] → [-3, -1, 2, 6]. Left-movers on the left and right-movers on the right can never meet.

Hints

1. Under what exact condition do two asteroids ever meet? Think about which is to the left and which direction each moves.
2. A left-moving asteroid only interacts with right-movers that are already to its left. Those are the most recently kept right-movers.
3. Keep a stack of survivors. When a left-mover arrives, pop right-movers smaller than it, stop if it hits an equal or larger one, and only push it if it survives.