Introduction

If you have been building your stack skills through problems like Valid Parentheses, Next Greater Element, and Backspace String Compare, then LeetCode 735 Asteroid Collision is the problem where everything comes together. It is one of the most satisfying Medium problems on LeetCode because it feels like a real simulation — you are literally modelling asteroids flying through space and crashing into each other.

You can find the problem here — LeetCode 735 Asteroid Collision.

This article breaks everything down in plain English so that anyone — beginner or experienced — can understand exactly what is happening and why the stack is the perfect tool for this problem.

What Is the Problem Really Asking?

You have a row of asteroids moving through space. Each asteroid has a size and a direction:

1. Positive number → asteroid moving to the right
2. Negative number → asteroid moving to the left

All asteroids move at the same speed. When a right-moving asteroid and a left-moving asteroid meet head-on, they collide:

1. The smaller one explodes
2. If they are the same size, both explode
3. The bigger one survives and keeps moving

Two asteroids moving in the same direction never meet, so they never collide.

Return the final state of all surviving asteroids after every possible collision has happened.

Real Life Analogy — Cars on a Highway

Imagine a highway with cars driving in both directions. Cars going right are in one lane, cars going left are in another lane. Now imagine the lanes overlap at some point.

A small car going right crashes into a big truck going left — the car gets destroyed, the truck keeps going. Two equally sized cars crash — both are destroyed. A massive truck going right demolishes everything coming from the left until it meets something bigger or nothing at all.

That is exactly the asteroid problem. The stack helps us track which asteroids are still "alive" and moving right, waiting to potentially collide with the next left-moving asteroid that comes along.

Why Stack Is the Perfect Data Structure Here

The key observation is this — only a right-moving asteroid followed by a left-moving asteroid can collide. A left-moving asteroid might destroy several right-moving ones in a chain before it either survives or gets destroyed itself.

This chain reaction behavior — where the outcome of one collision immediately triggers the possibility of another — is exactly what a stack handles naturally. The stack holds right-moving asteroids that are still alive and waiting. When a left-moving asteroid arrives, it battles the top of the stack repeatedly until either it is destroyed or no more collisions are possible.

All Possible Collision Scenarios

Before looking at code it is important to understand every case that can happen:

Case 1 — Right-moving asteroid (ast[i] > 0) No collision possible immediately. Push it onto the stack and move on.

Case 2 — Left-moving asteroid, stack is empty Nothing to collide with. Push it onto the stack.

Case 3 — Left-moving asteroid, top of stack is also left-moving (negative) Two asteroids going the same direction never meet. Push it onto the stack.

Case 4 — Left-moving asteroid meets right-moving asteroid (collision!) Three sub-cases:

1. Stack top is bigger → left-moving asteroid explodes, stack top survives
2. Stack top is smaller → stack top explodes, left-moving asteroid continues (loop again)
3. Same size → both explode

The Solution — Stack Simulation

Step-by-Step Dry Run — asteroids = [10, 2, -5]

Let us trace exactly what happens:

Processing 10:

1. Stack is empty, no collision possible
2. survived = true → push 10
3. Stack: [10]

Processing 2:

1. Stack top is 10 (positive), current is 2 (positive) — same direction, no collision
2. survived = true → push 2
3. Stack: [10, 2]

Processing -5:

1. Stack top is 2 (positive), current is -5 (negative) — collision!
2. 2 < 5 → stack top smaller, pop 2. survived stays true
3. Stack: [10]
4. Stack top is 10 (positive), current is -5 (negative) — collision again!
5. 10 > 5 → stack top bigger, current asteroid destroyed. survived = false, break
6. Stack: [10]

survived = false → do not push -5

Final stack: [10] → output: [10] ✅

Step-by-Step Dry Run — asteroids = [3, 5, -6, 2, -1, 4]

Processing 3: stack empty → push. Stack: [3]

Processing 5: both positive, same direction → push. Stack: [3, 5]

Processing -6:

1. Collision with 5: 5 < 6 → pop 5. Stack: [3]
2. Collision with 3: 3 < 6 → pop 3. Stack: []
3. Stack empty → survived = true → push -6
4. Stack: [-6]

Processing 2: stack top is -6 (negative), current is 2 (positive) — same direction check fails, no collision → push. Stack: [-6, 2]

Processing -1:

1. Collision with 2: 2 > 1 → stack top bigger, -1 explodes. survived = false
2. Stack: [-6, 2]

Processing 4: stack top is 2 (positive), current is 4 (positive) — same direction → push. Stack: [-6, 2, 4]

Final stack: [-6, 2, 4] → output: [-6, 2, 4] ✅

Understanding the survived Flag

The survived boolean flag is the most important design decision in this solution. It tracks whether the current asteroid makes it through all collisions.

It starts as true — we assume the asteroid survives until proven otherwise. It only becomes false in two situations — when the stack top is bigger (current asteroid destroyed) or when both are equal size (mutual destruction). If survived is still true after the while loop, the asteroid either won all its battles or never had any — either way it gets pushed onto the stack.

This flag eliminates the need for complicated nested conditions and makes the logic clean and readable.

Building the Result Array

One important detail — when you pop everything from a stack to build an array, the order is reversed. The stack gives you elements from top to bottom (last to first). So we fill the result array from the end to the beginning using i = ans.length - 1 going down to 0. This preserves the original left-to-right order of surviving asteroids.

Time and Space Complexity

Time Complexity: O(n) — each asteroid is pushed onto the stack at most once and popped at most once. Even though there is a while loop inside the for loop, each element participates in at most one push and one pop across the entire run. Total operations stay linear.

Space Complexity: O(n) — in the worst case (all asteroids moving right, no collisions) all n asteroids sit on the stack simultaneously.

Common Mistakes to Avoid

Forgetting that same-direction asteroids never collide The collision condition is specifically st.peek() > 0 && ast[i] < 0. Two positive asteroids, two negative asteroids, or a negative followed by a positive — none of these collide. Only right then left.

Not using a loop for chain collisions A single left-moving asteroid can destroy multiple right-moving ones in sequence. If you only check the stack top once instead of looping, you will miss chain destructions like in the [3, 5, -6] example.

Forgetting the survived flag and always pushing Without the flag, a destroyed asteroid still gets pushed onto the stack, giving wrong results.

Wrong array reconstruction from stack Forgetting that stack order is reversed and filling the array from left to right gives a backwards answer. Always fill from the last index downward.

How This Problem Differs From Previous Stack Problems

Every previous stack problem in this series had a simple push-or-pop decision per character. Asteroid Collision introduces something new — a while loop inside the for loop. This is because one incoming asteroid can trigger multiple consecutive pops (chain collisions). The stack is no longer just storing history — it is actively participating in a simulation where multiple stored elements can be affected by a single incoming element.

This is the defining characteristic of harder stack problems and is exactly what appears in problems like Largest Rectangle in Histogram and Trapping Rain Water.

FAQs — People Also Ask

Q1. Why is a Stack used to solve LeetCode 735 Asteroid Collision? Because right-moving asteroids wait on the stack until a left-moving asteroid arrives. The left-moving asteroid battles the top of the stack repeatedly — this LIFO chain reaction behavior is exactly what a stack handles naturally and efficiently.

Q2. What is the time complexity of LeetCode 735? O(n) time because each asteroid is pushed and popped at most once regardless of how many chain collisions happen. Space complexity is O(n) for the stack in the worst case.

Q3. When do two asteroids NOT collide in LeetCode 735? Two asteroids never collide when both move right (both positive), both move left (both negative), or when a left-moving asteroid comes before a right-moving one — they move away from each other in that case.

Q4. Is LeetCode 735 asked in coding interviews? Yes, it is commonly asked at companies like Amazon, Google, and Microsoft as a Medium stack problem. It tests whether you can handle simulation problems with multiple conditional branches and chain reactions — skills that translate directly to real world system design thinking.

Q5. What is the difference between LeetCode 735 and LeetCode 496 Next Greater Element? Both use a stack and involve comparing elements. In Next Greater Element, you search forward for something bigger. In Asteroid Collision, collisions happen between the current element and stack contents, and the current element might destroy multiple previous elements in a chain before settling. The collision logic in 735 is more complex.

Similar LeetCode Problems to Practice Next

1. 496. Next Greater Element I — Easy — monotonic stack pattern
2. 739. Daily Temperatures — Medium — next greater with index distance
3. 1047. Remove All Adjacent Duplicates In String — Easy — chain removal with stack
4. 84. Largest Rectangle in Histogram — Hard — advanced stack simulation
5. 503. Next Greater Element II — Medium — circular array with monotonic stack

Conclusion

LeetCode 735 Asteroid Collision is a wonderful problem that takes the stack simulation pattern to the next level. The key insight is recognizing that only right-then-left asteroid pairs can collide, that chain collisions require a while loop not just an if statement, and that the survived flag keeps the logic clean across all cases.

Work through every dry run in this article carefully — especially the [3, 5, -6, 2, -1, 4] example — because seeing chain collisions play out step by step is what makes this pattern click permanently.

Once this problem makes sense, you are genuinely ready for the harder stack problems that follow. Keep going!