Skip to main content
Talentd

Asteroid Collision - Solution & Explanation

MediumArrayStackSimulation14 min readAsked at: Amazon, Microsoft, Goldman Sachs +29
Practice this problem

Problem Statement

We are given an array asteroids of integers representing asteroids in a row. The indices of the asteriod in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

 

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

 

Constraints:

  • 2 <= asteroids.length <= 104
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

Approach Overview

Problem Overview: You are given an array where each value represents an asteroid's size and direction. Positive values move right, negative values move left. When two asteroids moving in opposite directions meet, the smaller one explodes. If both are equal, both disappear. The task is to simulate these collisions and return the asteroids that remain.

Approach 1: Stack-Based Simulation (O(n) time, O(n) space)

This approach models the collision process using a stack. Iterate through the array and push asteroids moving right onto the stack. When a left-moving asteroid appears, it may collide with right-moving asteroids stored on the stack. Repeatedly compare the top of the stack with the incoming asteroid and resolve collisions by removing the smaller one. Equal sizes remove both. Each asteroid enters and leaves the stack at most once, which keeps the time complexity linear. This pattern is common in stack problems where elements interact with the most recent unresolved item.

The key insight is that collisions only happen when the previous asteroid moves right and the current one moves left. All other combinations never meet, so they can be pushed safely. This approach directly simulates the physics of the problem and works well for interview settings because the logic is easy to reason about and efficient.

Approach 2: Two Pointer Technique (O(n) time, O(1) extra space)

This variation treats the input array itself as the structure that stores surviving asteroids. Use one pointer to iterate through the array and another pointer to represent the position where the next surviving asteroid should be written. When a collision scenario appears, repeatedly compare the current asteroid with the last stored asteroid and resolve outcomes in place. The pointer moves backward when an asteroid is destroyed and forward when a survivor is confirmed.

This approach avoids an explicit stack by reusing the array as a simulated stack. The logic still mirrors the same collision rules: only right-moving asteroids before a left-moving asteroid can collide. Because each asteroid is processed a constant number of times, the runtime remains O(n). It is essentially an in-place simulation built on top of an array.

Recommended for interviews: The stack-based solution is what most interviewers expect. It clearly demonstrates understanding of collision conditions and stack behavior while maintaining O(n) time complexity. The two pointer version is a space-optimized refinement that shows deeper understanding of how stacks can be simulated in arrays.

Approach 1: Stack-Based Approach

This approach leverages a stack data structure to resolve collisions. We maintain a stack to keep track of the rightward-moving asteroids and resolve them when encountering leftward-moving asteroids. If the stack is empty or the asteroid is moving right, simply push it onto the stack. When encountering a leftward-moving asteroid, compare it to the stack's top. If the sizes are equal, both asteroids explode; if the stack's top is smaller, the stack's top asteroid explodes; otherwise, the current leftward-moving asteroid does not survive. Iterate through the entire list with these rules to achieve the desired result.

The function asteroidCollision initializes an empty list as a stack. It iterates over each asteroid and checks for a collision condition and resolves it by comparing the stack's top value with the current asteroid. Depending on the conditions, it either pops from the stack or appends to it while iterating through the entire list.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n). Each asteroid is pushed and popped from the stack at most once.
Space Complexity: O(n). In the worst case, all asteroids are moving in the same direction and are all stored in the stack.

Try this approach in the editor →

Approach 2: Two Pointer Technique

This method involves using two pointers to manage the movement of asteroids in the array, with no additional stack usage. Although usually less intuitive than a stack approach, the two-pointer solution iteratively resolves collisions simultaneously moving both pointers forward and backward depending on conditions. However, a true two-pointer solution for asteroid collisions is typically not the ideal choice here compared to a stack-based method in terms of simplicity and efficiency.

This Java solution uses a Stack to properly manage asteroid collisions through a similar logic to the Python sample. The stack checks for ongoing collisions and resolves them according to magnitude. The final result is converted back to an array to meet function return requirements.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n) due to a single pass through the array.
Space Complexity: O(n) for potential stack usage in storing results.

Try this approach in the editor →

Approach 3: Stack

We traverse each asteroid x from left to right. Since each asteroid may collide with multiple asteroids before it, we consider using a stack to store.

  • For the current asteroid, if x>0, it will definitely not collide with the previous asteroid, and we can directly push x into the stack.
  • Otherwise, if the stack is not empty and the top element of the stack is greater than 0, and the top element of the stack is less than -x, then the top element of the stack corresponds to the asteroid will explode, we loop to the top element of the stack Pop out until the condition is not satisfied. At this time, if the top element of the stack is equal to -x, then the two asteroids will explode, and we only need to pop the top element of the stack; if the stack is empty, or the top element of the stack is less than 0, then the current asteroid will not collide, we will push x into the stack.

Finally, we return the elements in the stack as the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array asteroids.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Approach

Time Complexity: O(n). Each asteroid is pushed and popped from the stack at most once.
Space Complexity: O(n). In the worst case, all asteroids are moving in the same direction and are all stored in the stack.

Two Pointer Technique

Time Complexity: O(n) due to a single pass through the array.
Space Complexity: O(n) for potential stack usage in storing results.

Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based SimulationO(n)O(n)General case. Easiest to implement and most commonly expected in interviews.
Two Pointer In-Place SimulationO(n)O(1)When minimizing extra memory or demonstrating in-place stack simulation.

Video Solution

Asteroid Collision - Stack - Leetcode 735 • NeetCode • 75,180 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Asteroid Collision easy or hard?
Asteroid Collision is classified as a Medium problem. The challenge lies in handling multiple consecutive collisions and edge cases where several asteroids are destroyed in sequence. Once the stack simulation pattern is understood, the implementation becomes straightforward.
Asteroid Collision Python/Java solution
Python solutions typically use a list as a stack and simulate collisions with while loops that compare the stack top and the incoming asteroid. Java implementations often use Stack or ArrayDeque, while C++ commonly uses vector or stack. All follow the same O(n) collision simulation logic.
How to solve Asteroid Collision in O(n)?
Iterate through the array while maintaining a stack of surviving asteroids. Push positive values directly. When encountering a negative value, repeatedly compare it with the stack top while the top asteroid moves right. Remove the smaller asteroid until the collision is resolved or the stack becomes safe to push the new asteroid.
What is the best approach for Asteroid Collision?
The stack-based simulation is the most common and interview-friendly approach. It processes asteroids from left to right while storing unresolved right-moving asteroids in a stack. When a left-moving asteroid appears, collisions are resolved by comparing sizes with the stack top. This guarantees O(n) time since each asteroid is pushed and popped at most once.
Is Asteroid Collision asked at Google/Amazon/Meta?
Asteroid Collision is a common medium-level interview problem that appears in preparation lists for companies like Amazon, Google, and Meta. It tests stack usage, edge case handling, and simulation logic. Variants of collision or elimination simulations frequently appear in technical interviews.
What data structure is used in Asteroid Collision?
A stack is the primary data structure used to track surviving asteroids. It stores right-moving asteroids that may collide with future left-moving ones. The stack structure naturally models the 'last unresolved element' behavior required for collision checks.
What is the time complexity of Asteroid Collision?
The optimal solution runs in O(n) time where n is the number of asteroids. Each asteroid is processed once and may be pushed or popped from the stack at most one time. Space complexity is O(n) for the stack, although an in-place simulation can reduce extra space to O(1).

Ready to solve this problem?

Practice Asteroid Collision with our built-in code editor and test cases.

Practice on FleetCode
Previous

Can Place Flowers

Next

Count Collisions on a Road