Asteroid Collision

Asteroid Collision

What is this problem about?

The Asteroid Collision interview question simulates a row of asteroids moving in space. Each asteroid has a size (absolute value) and a direction (positive for right, negative for left). When two asteroids collide, the smaller one explodes. If they are the same size, both explode. Asteroids moving in the same direction or moving away from each other never collide. This Asteroid Collision coding problem is a perfect simulation of stack-based interaction.

Why is this asked in interviews?

This is a high-frequency question at companies like Apple, Google, and Amazon. It tests if a candidate can recognize that only "local" interactions (the rightmost asteroid and the incoming left-moving asteroid) determine the next state. It evaluates your ability to handle complex "while" loop conditions within a traversal.

Algorithmic pattern used

The Array, Simulation, Stack interview pattern is the standard solution. You use a stack to keep track of asteroids moving to the right. When you encounter an asteroid moving to the left, you compare it with the top of the stack and resolve the collisions until the left-moving asteroid is destroyed or the stack no longer has right-moving asteroids.

Example explanation

Asteroids: [5, 10, -5]

1. 5: Moving right, push to stack. Stack: [5]
2. 10: Moving right, push to stack. Stack: [5, 10]
3. -5: Moving left. Compare with top (10). 10 is larger, so -5 explodes. Result: [5, 10]. If it was [10, 2, -5], then -5 would destroy 2, then collide with 10 and explode.

Common mistakes candidates make

• Incorrect Collision Logic: Colliding asteroids that are moving away from each other (e.g., [-2, 5]). These will never hit.
• Missing Both-Explode Case: Forgetting that if a 5 and -5 collide, both should be removed.
• Nested Loop Complexity: Not handling the stack resolution efficiently, leading to confusion about which asteroid is currently being processed.

Interview preparation tip

Whenever you have elements that "interact" or "cancel each other out" based on their order, think of a Stack. It allows you to focus on the most recent "active" element and resolve its fate before moving on.