Asteroid Collision in Python – LeetCode75 Explained

The Asteroid Collision problem from LeetCode75 is a classic stack-based challenge that tests your ability to simulate collisions and apply logical reasoning step by step. It is a common coding interview problem because it combines array traversal, condition handling and stack operations into one neat exercise.

In this blog, we’ll break down the problem statement, explore examples and provide a step-by-step Python solution with explanations so you can master this problem with confidence.

Problem Statement

We are given an array asteroids of integers representing asteroids moving in a row.

• Each asteroid’s absolute value represents its size.
• The sign represents its direction:
  • Positive → moving right
  • Negative → moving left

All asteroids move at the same speed.

If two asteroids meet:

• The smaller one explodes.
• If both are the same size, both explode.
• Two asteroids moving in the same direction will never meet.

Return the state of the asteroids after all collisions.

Understanding the Problem

The trick here is to realize that only right-moving asteroids (> 0) can collide with left-moving asteroids (< 0). When they collide, the smaller asteroid is destroyed. If they’re the same size, both are destroyed.

This problem is best solved using a stack:

• Push asteroids moving right into the stack.
• When a left-moving asteroid comes, check for collisions with the top of the stack.
• Resolve collisions until the asteroid is either destroyed or safely added to the stack.

Examples

Example 1

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

Explanation: 10 destroys -5.

Example 2

Input: asteroids = [8, -8]
Output: []

Explanation: Both asteroids are equal in size and destroy each other.

Example 3

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

Explanation: 2 is destroyed by -5, then 10 destroys -5.

Example 4

Input: asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]

Explanation: No collisions occur because they move in opposite directions without meeting.

Complete Python Solution

from typing import List

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = []

        for asteroid in asteroids:
            # Check for collision
            while stack and asteroid < 0 and stack[-1] > 0:
                if abs(asteroid) > stack[-1]:
                    stack.pop()  # smaller asteroid explodes
                    continue
                elif abs(asteroid) == stack[-1]:
                    stack.pop()  # both explode
                break
            else:
                stack.append(asteroid)  # no collision

        return stack

Python Solution – Step by Step

Step 1: Initialize a Stack

We’ll use a stack to keep track of asteroids that are still “alive.”

stack = []

Step 2: Traverse the Asteroids

Loop through each asteroid to check its direction and potential collisions.

for asteroid in asteroids:

Step 3: Handle Collisions

Collisions only happen if the top of the stack is moving right (> 0) and the current asteroid is moving left (< 0).

while stack and asteroid < 0 and stack[-1] > 0:
    if abs(asteroid) > stack[-1]:
        stack.pop()  # right-moving asteroid explodes
        continue
    elif abs(asteroid) == stack[-1]:
        stack.pop()  # both explode
    break

Step 4: Return the Remaining Asteroids

If no collision occurs, or if the current asteroid survives, append it to the stack.

else:
    stack.append(asteroid)

Why This Solution Works

• Stack structure naturally models the sequence of collisions.
• Only right → left interactions matter, so we avoid unnecessary checks.
• By continuously resolving collisions before adding new asteroids, we guarantee correctness.

Time and Space Complexity

• Time Complexity: O(n), since each asteroid is processed once and may cause some pops.
• Space Complexity: O(n), for the stack in the worst case (no collisions).

Edge Cases

Input	Output	Explanation
[1, -1]	[]	Both equal size → both explode.
[10, -2, -3]	[10]	10 survives after destroying both.
[-5, 5]	[-5, 5]	Different directions, no collision.
[5, 6, 7, -10]	[-10]	-10 destroys all smaller right-movers.

Real-World Applications

This problem simulates scenarios where opposite forces collide and resolve:

• Physics simulations of particles or objects in motion.
• Stock market analysis where opposing trades cancel out.
• Game development for modeling collisions between moving entities.
• Network traffic where opposing signals neutralize or override each other.

Conclusion

The Asteroid Collision (LeetCode 75) problem is an excellent example of applying stacks to simulate real-world events. By carefully handling each asteroid and resolving collisions step by step, we achieve a clean and efficient O(n) solution.

Practicing this challenge improves your ability to model dynamic interactions with stacks—an essential skill for coding interviews and problem-solving in areas like simulation, physics and data stream processing.

Related Reads

• Introduction to Large Language Models: IIT Madras YouTube Course
• Removing Stars From a String in Python – LeetCode75 Clearly Explained
• Equal Row and Column Pairs in Python – LeetCode75 Explained
• RAG From Scratch: A Complete Guide to Retrieval-Augmented Generation
• Determine if Two Strings Are Close in Python – LeetCode75 Explained

References

LeetCode – Asteroid Collision (Problem 735) – Official problem statement and community solutions.

GeeksforGeeks – Stack Data Structure – Fundamental concepts of stacks and their applications.

Big-O Cheat Sheet – Reference for analyzing time and space complexity.