Asteroid Collision

Published at23 Jul 2026

Stack Medium 2 views

Like0

You are given an array of asteroids moving in a straight line. The absolute value of each integer represents the size of the asteroid, and the sign represents its direction: positive moves right, negative moves left. When two asteroids meet, the larger one destroys the smaller one. If they are the same size, both explode. Asteroids moving in the same direction never collide.

A stack is the natural data structure here because collisions only happen between a right-moving asteroid (already on the stack) and a left-moving asteroid (just arriving). The top of the stack represents the most recent surviving asteroid that might collide with the next incoming asteroid.

When an asteroid arrives, if it is moving right (positive), it is pushed onto the stack because it cannot collide with any asteroid already on the stack (they are all moving left or already settled). If it is moving left (negative), it may collide with right-moving asteroids on the stack. While the top of the stack is a right-moving asteroid smaller than the incoming left-moving asteroid, the top is destroyed and popped. After this cleanup, if the top is an equal right-moving asteroid, both are destroyed. If the stack is empty or the top is also moving left, the incoming asteroid survives and is pushed.

This pattern is unique to the stack family because it combines conditional push/pop logic with simulation. Unlike bracket matching or monotonic stacks where the rule is fixed, the collision logic depends on both the direction and size of the asteroids, making it a more dynamic use of the stack.

The final stack contains the surviving asteroids in their original relative order, since the stack naturally preserves the sequence of surviving elements.

Example Input & Output

Example 1

Input

[10, 2, -5]

Output

[10]

Explanation

-5 collides with 2 first (2 < 5), destroying 2. Then -5 collides with 10 (5 < 10), destroying -5. Only 10 survives.

Example 2

Input

[5, 10, -5]

Output

[5, 10]

Explanation

10 and -5 collide. 10 is larger, so -5 is destroyed. 5 and 10 never collide (same direction).

Example 3

Input

[8, -8]

Output

[]

Explanation

Both are equal size, so both explode.

Algorithm Flow

Recommendation Algorithm Flow for Asteroid Collision

Solution Approach

Iterate through each asteroid. If the stack is empty or the current asteroid is positive, push it. If the current asteroid is negative, check for collision with the top of the stack (which must be positive). While the stack has a positive top that is smaller than the current asteroid’s absolute value, pop it. If the top is equal, pop and discard both. If the stack is empty or the top is negative, push the current asteroid.

function solution(asteroids) {
  const stack = []
  for (const a of asteroids) {
    if (a > 0) {
      stack.push(a)
    } else {
      while (stack.length && stack[stack.length - 1] > 0 && stack[stack.length - 1] < -a) {
        stack.pop()
      }
      if (stack.length && stack[stack.length - 1] === -a) {
        stack.pop()
      } else if (!stack.length || stack[stack.length - 1] < 0) {
        stack.push(a)
      }
    }
  }
  return stack
}

Time complexity is O(n). Space complexity is O(n) for the stack.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int[] solution(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int a : asteroids) {
            if (a > 0) {
                stack.push(a);
            } else {
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -a) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() == -a) {
                    stack.pop();
                } else if (stack.isEmpty() || stack.peek() < 0) {
                    stack.push(a);
                }
            }
        }
        int[] result = new int[stack.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = stack.get(i);
        }
        return result;
    }
}

javascript

function solution(asteroids) {
  var stack = [];
  for (var i = 0; i < asteroids.length; i++) {
    var a = asteroids[i];
    if (a > 0) {
      stack.push(a);
    } else {
      while (stack.length && stack[stack.length - 1] > 0 && stack[stack.length - 1] < -a) {
        stack.pop();
      }
      if (stack.length && stack[stack.length - 1] === -a) {
        stack.pop();
      } else if (!stack.length || stack[stack.length - 1] < 0) {
        stack.push(a);
      }
    }
  }
  return stack;
}

php

<?php
function solution($asteroids) {
    $stack = [];
    foreach ($asteroids as $a) {
        if ($a > 0) {
            array_push($stack, $a);
        } else {
            while (!empty($stack) && end($stack) > 0 && end($stack) < -$a) {
                array_pop($stack);
            }
            if (!empty($stack) && end($stack) === -$a) {
                array_pop($stack);
            } elseif (empty($stack) || end($stack) < 0) {
                array_push($stack, $a);
            }
        }
    }
    return $stack;
}

python

def solution(asteroids):
    stack = []
    for a in asteroids:
        if a > 0:
            stack.append(a)
        else:
            while stack and stack[-1] > 0 and stack[-1] < -a:
                stack.pop()
            if stack and stack[-1] == -a:
                stack.pop()
            elif not stack or stack[-1] < 0:
                stack.append(a)
    return stack

rust

fn solution(asteroids: Vec<i32>) -> Vec<i32> {
    let mut stack: Vec<i32> = Vec::new();
    for &a in &asteroids {
        if a > 0 {
            stack.push(a);
        } else {
            while let Some(&top) = stack.last() {
                if top <= 0 || top >= -a { break; }
                stack.pop();
            }
            if stack.is_empty() || *stack.last().unwrap() < 0 {
            stack.push(a);
        } else if *stack.last().unwrap() == -a {
            stack.pop();
        }
        }
    }
    stack
}

typescript

function solution(asteroids: number[]): number[] {
    var stack: number[] = [];
    for (var i = 0; i < asteroids.length; i++) {
        var a = asteroids[i];
        if (a > 0) {
            stack.push(a);
        } else {
            while (stack.length && stack[stack.length - 1] > 0 && stack[stack.length - 1] < -a) {
                stack.pop();
            }
            if (stack.length && stack[stack.length - 1] === -a) {
                stack.pop();
            } else if (!stack.length || stack[stack.length - 1] < 0) {
                stack.push(a);
            }
        }
    }
    return stack;
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Asteroid Collision

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Baseball Score Tracker

Backspace String Compare

Next Greater Element I

Decode String

Remove All Adjacent Duplicates in String

Basic Calculator II

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.