Asteroid Collisions

Problem Statement

You are given an array of integers representing asteroids in a row. Each asteroid moves at the same speed.

• Positive value = moving right
• Negative value = moving left
• Absolute value = size of the asteroid

When two asteroids meet (one moving right, next moving left), the smaller one explodes. If equal size, both explode. Asteroids moving in the same direction never meet.

Return the state of the asteroids after all collisions.

Constraints

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

Example

Input: [5, 10, -5]

Output: [5, 10]

Explanation: 10 and -5 collide → 10 survives. 5 and 10 move in same direction → no collision.

Input: [8, -8]

Output: []

Explanation: Equal size, both explode.

Input: [-2, -1, 1, 2]

Output: [-2, -1, 1, 2]

Explanation: Left-moving asteroids are to the left of right-moving ones → no collisions.

What the Interviewer Expects

1. Stack-based simulation — push right-moving asteroids. When a left-moving asteroid comes, resolve collisions with the stack top.
2. Collision loop — a single left-moving asteroid might destroy multiple right-moving ones before being destroyed itself (or surviving).
3. Three collision outcomes: left survives, right survives, both destroyed.
4. Edge cases: all same direction, alternating destroy chain, single asteroid.

Follow-ups

1. What if asteroids have different speeds? How does collision detection change?
2. What if the array is circular (last element can collide with first)?
3. Can you solve this without a stack using two pointers?
4. What's the maximum number of collisions possible for an array of size n?