Asteroid Collision | Leetcode 735 | Optimal Stack Solution

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.

Here’s the [Problem Link] to begin with.

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

Optimal Approach: Monotonic Stack Simulation

Intuition

• Use a stack to maintain asteroids that are stable so far.
• Push all right-moving asteroids directly; they can only collide with a future left-moving one.
• When encountering a left-moving asteroid, resolve collisions with the stack’s right-moving tops:
  • Pop all smaller right movers.
  • If the top has the same size, pop it and discard the current one (both explode).
  • If the stack is empty or top is a left mover, the current left mover survives; push it.

This simulates the process in a single pass with amortized O(1) per asteroid, leading to O(n) time.

Code

class Solution:
    def asteroidCollision(self, asteroids):

        # Size of the array
        n = len(asteroids)

        # List implementation of stack
        st = []

        # Traverse all the asteroids
        for i in range(n):

            # Push the asteroid in stack if a
            # right moving asteroid is seen
            if asteroids[i] > 0:
                st.append(asteroids[i])

            # Else if the asteroid is moving
            # left, perform the collisions
            else:

                # Until the right moving asteroids are
                # smaller in size, keep on destroying them
                while st and st[-1] > 0 and st[-1] < abs(asteroids[i]):

                    # Destroy the asteroid
                    st.pop()

                # If there is right moving asteroid
                # which is of same size
                if st and st[-1] == abs(asteroids[i]):

                    # Destroy both the asteroids
                    st.pop()

                # Otherwise, if there is no left
                # moving asteroid, the right moving
                # asteroid will not be destroyed
                elif not st or st[-1] < 0:

                    # Storing the array in final state
                    st.append(asteroids[i])

        # Return the final state of asteroids
        return st

How the Code Works (Conceptual Walkthrough)

• Right movers (positive) are appended since they won’t collide immediately.
• For a left mover (negative), it may collide with prior right movers:
  • While the top of the stack is a smaller right mover: pop it (it explodes).
  • If the top is the same size: pop it and do not push the current (both explode).
  • If the stack is empty or top is a left mover: push the current left mover (no collision now).
• This process ensures collisions are resolved in the correct order as they would occur on the line.

Time and Space Complexity

• Time: O(n) – each asteroid is pushed and popped at most once.
• Space: O(n) in the worst case for the stack (when no collisions happen).

Edge Cases and Tips

• All positives: return same list (no collisions).
• All negatives: return same list (no collisions).
• Equal sizes: both vanish.
• Large sequences of small positives followed by a big negative: the loop pops many items – still amortized O(n).

When to Use This Pattern

• Any linear collision or cancellation simulation with direction and magnitude can often be modeled with a stack (e.g., removing adjacent conflicts, evaluating left-right interactions).
• The key is to define when elements interact (here: positive followed by negative) and what rules resolve them.

This solution is concise, robust, and optimal for the Asteroid Collision problem, ready for interviews and production.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.