Stack · 105Medium
Asteroid Collision
An array asteroids gives asteroid sizes; the sign is the direction (positive means right, negative left). Colliding asteroids destroy the smaller one, or both if equal. Asteroids moving the same way never meet. Return the final state.
Constraints
- 2 <= asteroids.length <= 10^4
- -1000 <= asteroids[i] <= 1000, and asteroids[i] != 0
Examples
asteroidCollision([5, 10, -5]) -> [5, 10] asteroidCollision([8, -8]) -> [] // equal sizes destroy each other asteroidCollision([10, 2, -5]) -> [10] asteroidCollision([-2, 2]) -> [-2, 2] // moving apart, never collide asteroidCollision([5, -5, 5]) -> [5] // pair annihilates, the last survives asteroidCollision([3, 1, -4]) -> [-4] // one asteroid destroys a whole chain
Edge cases
- A collision only happens when a positive is immediately left of a negative.
- One asteroid may destroy several in a chain.
- Equal sizes destroy BOTH.
Show the target complexity (spoiler)
- Naive
- Repeatedly scanning the array for a colliding pair until stable is O(n^2).
- Target
- O(n) time, O(n) space — a stack: on a negative asteroid, pop while the top is a smaller positive, and only push if it survives.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/04-stack/105-asteroid-collision.js ./practice c 105