Asteroid Collision

medium

We are given an array asteroids representing asteroids in a row. For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one explodes. If both are the same size, both explode. Two asteroids moving in the same direction will never meet.

Test Cases

Copy an input into the main harness and Run to verify

Input

asteroids = [5,10,-5]

Expected Output

[5,10]

Explanation: The 10 and -5 collide, and the -5 explodes. The 5 and 10 never meet.

Input

asteroids = [8,-8]

Expected Output

[]

Explanation: They are the same size, so both explode.

Input

asteroids = [10,2,-5]

Expected Output

[10]

Explanation: The 2 and -5 collide leaving -5, which then collides with 10 and explodes.

Constraints

2 <= asteroids.length <= 10^4
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

Hints

Hint 1 — click to reveal

A collision happens only when a positive asteroid is followed by a negative one.

Hint 2 — click to reveal

A stack of surviving asteroids lets an incoming left-mover chew through several right-movers in turn.

Java Compiler