486. Asteroid Collision
A row of asteroids asteroids floats along a line. Each entry is a nonzero integer: its absolute value is the asteroid's size and its sign is its direction — positive drifts right, negative drifts left. All asteroids share one speed, so overtaking never happens — only head-on meetings matter.
When two asteroids meet head-on, the smaller one shatters; if they are the same size, both shatter. A left-mover that already sits to the left of a right-mover never meets it — the two just drift further apart.
Return the asteroids that remain after every possible collision has played out, in their original relative order. Note that one asteroid may destroy several others before it is stopped (or escapes).
Example 1:
Input: asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: The -5 drifts left into the 10; since 10 is bigger, the -5 shatters. 5 and 10 both move right at the same speed, so they never touch.
Example 2:
Input: asteroids = [10, 2, -5]
Output: [10]
Explanation: The -5 first meets the 2 and destroys it, then continues left into the 10 and shatters against it. Only the 10 survives.
Constraints:
- 2 ≤ asteroids.length ≤ 10⁴
- -1000 ≤ asteroids[i] ≤ 1000
- asteroids[i] ≠ 0
Hints:
Work out which pairs can actually collide: only a right-mover with a left-mover somewhere to its right. Two right-movers, two left-movers, or a negative followed by a positive (moving apart) are all permanently safe.
Process asteroids left to right and keep the survivors so far. A new left-mover can only crash into the most recent surviving right-mover — exactly the thing a stack's top gives you.
Keep popping while the incoming negative outweighs the positive on top. Stop when it shatters (top is bigger), when both shatter (equal sizes), or when the stack has no right-mover left — only then does the incoming asteroid get pushed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: asteroids = [5, 10, -5]
Expected output: [5, 10]