MediumCoding

Asteroid Collision

Asked at

Amazon

Microsoft

Myntra

Qualcomm

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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

The **absolute value **of an asteroid represents its size. The sign of an asteroid represents its direction: positive (+) means moving right, negative (-) means moving left.

Collision rules:

Asteroids moving in the same direction never collide.
When two asteroids moving in opposite directions collide, the smaller asteroid explodes and the larger asteroid continues moving in the same direction.
If both asteroids are equal in size, both explode.
Collisions are resolved one at a time, from left to right. If an asteroid survives a collision, it continues moving and may collide immediately with the next asteroid in its path.

Return the **state **of the **asteroids **after all collisions as an array in the same order.

**Input: **asteroids = [1, 2, 3, -4, -2] Output: [-4, -2] Explanation:

Asteroid 3 and -4 collide → 3 explodes, -4 survives.
Asteroid -4 continues and collides with 2 → 2 explodes, -4 continues.
Asteroid -4 collides with 1 → 1 explodes, -4 continues.
Next asteroid -2 is moving left → no collision. Final state: [-4, -2].

Input: asteroids = [5, 10, -5, -10, 8, -8, -3, 12] Output: [5, 12] Explanation:

Asteroid 10 and -5 collide → -5 explodes, 10 survives.
Asteroid 10 and -10 collide → both explode.
Asteroid 8 and -8 collide → both explode.
Asteroid -3 moves left → collides with 5 (right-moving) → 5 > 3 → -3 explodes, 5 survives.
Asteroid 12 moves right → no collision with 5 because it is behind → 12 survives. Final state: [5, 12]

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

· 2 <= asteroids.length <= 105 · -106 <= asteroids[i] <= 106 · asteroids[i] != 0

cpp

class Solution{
public:
    vector<int> asteroidCollision(vector<int> &asteroids){
      
    }
};

java

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
    
    }
}

python

class Solution:
    def asteroidCollision(self, asteroids):

javascript

class Solution {
    asteroidCollision(asteroids) {
     
    }
}

csharp

public class Solution
{
    public List<int> AsteroidCollision(List<int> asteroids)
    {
      
    }
}

func asteroidCollision(asteroids []int) []int {

}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Use a stack to store asteroids that have survived everything processed so far.
02A collision is possible only when the stack top is positive and the current asteroid is negative.
03Resolve smaller, equal, and larger absolute-size cases until the current asteroid is destroyed or safe.
04Append the current asteroid only if it survives the entire collision loop.

Reference answer

Process asteroids from left to right and keep a stack of survivors. Most pairs cannot collide: a collision is possible only when the previous survivor moves right (stack.top > 0) and the current asteroid moves left (current < 0).

For that opposing pair, compare stack.top with abs(current). If the top is smaller, pop it and continue the loop because the current asteroid may hit another earlier survivor. If the sizes are equal, pop the top and mark the current asteroid destroyed. If the top is larger, the current asteroid is destroyed and the stack is unchanged. If the loop ends because there is no opposing positive top, append the surviving current asteroid.

Asteroids moving left behind another left-moving asteroid, or right behind another right-moving asteroid, never collide. Each asteroid is pushed once and popped at most once, so despite the inner loop the total time is O(n). The stack uses O(n) space. A clear alive flag often makes the three collision outcomes less error-prone.

Then expect these follow-ups

Why is the solution O(n) despite the nested while loop?
Tests: amortized analysis
Which sign ordering is the only one that can produce a collision?
Tests: case analysis

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question