Asteroid Collision

Medium· stack· simulation

Problem

Asteroids sit in a row; the absolute value is the size and the sign is the direction (positive moves right, negative moves left). When two meet, the smaller one explodes, and equal sizes both explode. Return the asteroids that remain after all collisions.

Examples

Input: asteroids = [5,10,-5]

Output: [5,10]

-5 hits 10 and is destroyed.

Input: asteroids = [10,2,-5]

Output: [10]

-5 destroys 2, then is destroyed by 10.

Constraints

• 2 <= asteroids.length <= 10^4
• asteroids[i] is non-zero, |asteroids[i]| <= 1000

Hints & approach

Hint 1

A collision only happens when a left-moving asteroid meets a right-moving one to its left.

Hint 2

Keep the survivors so far on a stack.

Hint 3

A new negative asteroid may destroy several positives on top of the stack.

Approachtry the hints first

Process asteroids left to right with a stack of survivors. For a negative asteroid, while the stack top is positive and smaller than its size, pop it. Then if the top is positive and equal in size, pop it and drop the new asteroid too; if the top is positive and larger, drop the new asteroid; otherwise push it. Positive asteroids are always pushed. Each asteroid is pushed and popped at most once.

Time O(n) · Space O(n)

← PreviousDecode String Next →Basic Calculator