Asteroid Collision
mediumLinked List & Stack II+20 XPTime limit 2s
Asteroids fly along a straight line, all at the same speed. Each is given by a non-zero integer: its absolute value is its size, and its sign is its direction (positive = moving right, negative = moving left). The list is in the order the asteroids sit on the line, left to right.
When a right-mover meets a left-mover, the smaller one explodes; if they are the same size, both explode. Two asteroids moving the same way never meet. Print what is left after all collisions.
Input:
- line 1:
n - line 2:
nnon-zero integers
Output: the surviving asteroids in order on one line, or empty if none survive.
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ |value| ≤ 1000.
Think about it: keep the survivors so far on a stack. A new left-mover keeps fighting the right-movers on top of the stack until it explodes, they are gone, or the top is also a left-mover. Each asteroid is pushed and popped at most once.
Sample input 1
3 5 10 -5
Sample output 1
5 10
Sample input 2
2 8 -8
Sample output 2
empty
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).