Skills101
← All coding problems

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: n non-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).

Loading editor…

Log in to run and submit your code — it's free.