Asteroid Collision

Medium
75.

Asteroid Collision

Asteroid Collision is a medium coding problem on arrays, simulation and stack, asked in PhonePe, Sprinklr, Myntra and Dream11 interviews.

Asteroids move along a row: the absolute value is the size, the sign is the direction (positive → right, negative → left), all at equal speed.

When two asteroids meet, the smaller explodes (both explode if equal). Asteroids moving the same direction never meet. Return the state after all collisions.

Example 1

Input
asteroids = [5,10,-5]
Output
[5,10]
Explanation
10 destroys -5.

Example 2

Input
asteroids = [8,-8]
Output
[]
Explanation
Equal sizes — both explode.

Example 3

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

Constraints

  • 2 <= asteroids.length <= 30
  • -100 <= asteroids[i] <= 100, asteroids[i] != 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
var asteroidCollision = function(asteroids) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Asteroid Collision — Solution in Python, Java & C++

Asteroid Collision solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Asteroid Collision is a medium coding problem on arrays, simulation and stack, asked in PhonePe, Sprinklr, Myntra and Dream11 interviews.

Problem statement

Asteroids move along a row: the absolute value is the size, the sign is the direction (positive → right, negative → left), all at equal speed.

When two asteroids meet, the smaller explodes (both explode if equal). Asteroids moving the same direction never meet. Return the state after all collisions.

Example 1

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: 10 destroys -5.

Example 2

Input: asteroids = [8,-8]
Output: []
Explanation: Equal sizes — both explode.

Example 3

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

Constraints

  • 2 <= asteroids.length <= 30
  • -100 <= asteroids[i] <= 100, asteroids[i] != 0

Hints for Asteroid Collision

  1. Hint 1

    Only a right-mover on the stack and an incoming left-mover collide.

  2. Hint 2

    Resolve collisions in a loop: the incoming asteroid may destroy several stack tops.

How to solve Asteroid Collision

There is exactly one collision pattern: something already moving right with something arriving that moves left. Every other pairing — two right-movers, two left-movers, or a left-mover already settled followed by a right-mover — drifts apart forever. So keep the settled asteroids on a stack and only fight when that one pattern appears.

Approach

  1. Process asteroids left to right, keeping the survivors on a stack.
  2. For the incoming asteroid a, loop while a is moving left (a < 0) and the top of the stack is moving right (top > 0) — the only collision case.
  3. If the top is smaller than |a|, it explodes: pop it and keep looping, because a may plough into the next one too.
  4. If they are the same size, both explode: pop the top and mark a dead.
  5. If the top is bigger, a explodes and the top survives — stop.
  6. If a survived the loop, push it.

Why it works

The stack always holds a settled configuration: no two asteroids in it can ever collide, because any right-mover sits above every left-mover that precedes it. A new asteroid can only disturb that from the right end, so resolving it against the top repeatedly is enough. Each asteroid is pushed once and popped at most once, so the cascading while still costs linear time overall.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The collision test needs both conditions. Checking only a < 0 makes left-movers wrongly attack other left-movers already on the stack.
  • Equal sizes destroy both asteroids — pop the top and stop the incoming one from being pushed.
  • Keep looping after a win: one large left-mover can wipe out a whole run of right-movers.
  • Compare magnitudes, not signed values: the incoming asteroid's size is -a when a is negative.

Reference solution

Python

from typing import List

def asteroidCollision(asteroids: List[int]) -> List[int]:
    st = []
    for a in asteroids:
        alive = True
        while alive and a < 0 and st and st[-1] > 0:
            top = st[-1]
            if top < -a:
                st.pop()
            elif top == -a:
                st.pop()
                alive = False
            else:
                alive = False
        if alive:
            st.append(a)
    return st

Java

public static int[] asteroidCollision(int[] asteroids) {
    int[] st = new int[asteroids.length];
    int top = 0;
    for (int a : asteroids) {
        boolean alive = true;
        while (alive && a < 0 && top > 0 && st[top - 1] > 0) {
            int t = st[top - 1];
            if (t < -a) {
                top--;
            } else if (t == -a) {
                top--;
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) st[top++] = a;
    }
    return Arrays.copyOf(st, top);
}

C++

vector<int> asteroidCollision(vector<int>& asteroids) {
    vector<int> st;
    for (int a : asteroids) {
        bool alive = true;
        while (alive && a < 0 && !st.empty() && st.back() > 0) {
            int t = st.back();
            if (t < -a) {
                st.pop_back();
            } else if (t == -a) {
                st.pop_back();
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) st.push_back(a);
    }
    return st;
}

JavaScript

var asteroidCollision = function(asteroids) {
    const st = [];
    for (const a of asteroids) {
        let alive = true;
        while (alive && a < 0 && st.length > 0 && st[st.length - 1] > 0) {
            const top = st[st.length - 1];
            if (top < -a) {
                st.pop();
            } else if (top === -a) {
                st.pop();
                alive = false;
            } else {
                alive = false;
            }
        }
        if (alive) st.push(a);
    }
    return st;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure