Problem Overview — Asteroids Moving Right and Left, Collisions by Size
LeetCode 735 Asteroid Collision gives you an integer array where each element represents an asteroid. The absolute value of an integer is the size of the asteroid, and the sign indicates direction: positive integers move to the right, and negative integers move to the left. All asteroids move at the same speed. You must return the state of the asteroids after all collisions.
When two asteroids meet — a right-moving (positive) and a left-moving (negative) — they collide. The smaller asteroid is destroyed. If they are the same size, both are destroyed. Two asteroids moving in the same direction never collide. The surviving asteroids are returned in their original order, with destroyed ones removed.
The problem is a clean simulation task: model the process as a stack where asteroids accumulate and collide against the stack top. The stack approach processes each asteroid exactly once and handles cascading collisions naturally through a while loop, making it one of the cleanest applications of the stack data structure in the LeetCode problem set.
- 1 <= asteroids.length <= 10^4
- −1000 <= asteroids[i] <= 1000, asteroids[i] != 0
- Positive value = moving right, negative value = moving left
- Collision occurs only between right-moving and left-moving asteroids
- Larger asteroid survives; equal size destroys both
- Return array of surviving asteroids in their original relative order
When Do Collisions Happen — Right Meets Left Is the Only Dangerous Pair
Only one combination of adjacent asteroids can cause a collision: a right-moving (positive) asteroid followed by a left-moving (negative) asteroid. When these two are adjacent — or when a left-moving asteroid reaches the back of a growing stack of right-movers — a collision occurs. All other pairings are safe: two positives diverge, two negatives diverge, and a negative before a positive diverges (they move away from each other).
A negative asteroid after a positive asteroid is the collision trigger. For example, in [5, -3], the -3 asteroid is moving left and the 5 is moving right — they will collide. But in [-3, 5], the -3 is already to the left of 5 and moving further left while 5 moves right — no collision. The relative position combined with direction determines whether a collision is possible.
The stack models the current set of right-movers in order. When you encounter a negative asteroid, you compare it against the stack top. If the top is positive, a collision is triggered. The while loop continues until the current negative asteroid is either destroyed, encounters an empty stack, or encounters a negative stack top (two negatives moving left together, no collision).
Collision Condition — Stack Top Positive and Current Negative
Collisions only occur when the stack top is positive (right-moving) and the current asteroid is negative (left-moving). All other combinations are safe to push directly: positive current always pushes, negative current with negative or empty stack always pushes, and negative current with positive stack top triggers the collision while loop. Keep this rule in mind and the collision logic becomes straightforward.
Stack Simulation — Iterate, Compare, Pop or Push at Each Step
The algorithm iterates through every asteroid in the input array. For each positive asteroid, it is pushed directly onto the stack — it moves right and will only collide with future left-movers. For each negative asteroid, a collision check begins: while the stack is non-empty and the stack top is positive, compare absolute sizes.
Inside the collision while loop: if the absolute value of the current negative asteroid is greater than the stack top, pop the stack top (it is destroyed) and continue the while loop — the current asteroid may collide with the next positive on the stack. If the absolute value equals the stack top, pop the stack top and discard the current asteroid (both destroyed) — break out of the while loop without pushing. If the absolute value is less than the stack top, discard the current asteroid — it is destroyed — and break without pushing.
After the while loop exits (either because the stack is empty or the stack top is negative), if the current asteroid survived, push it onto the stack. The final stack contents are the surviving asteroids in their original order. Returning the stack as an array gives the answer.
- 1Initialize empty stack
- 2For each asteroid in input array:
- 3 If positive: push directly onto stack
- 4 If negative: enter collision while loop
- 5 While stack non-empty AND stack top is positive:
- 6 If |current| > stack top: pop stack top, continue loop
- 7 If |current| == stack top: pop stack top, mark current destroyed, break
- 8 If |current| < stack top: mark current destroyed, break
- 9 If current survived (not destroyed): push onto stack
- 10Return stack as result array
Three Collision Outcomes — Win, Lose, or Tie for Each Collision Pair
Every individual collision between the current left-moving asteroid and the stack-top right-moving asteroid has exactly three outcomes. Current wins: the current asteroid is larger in absolute value, the stack top is destroyed (popped), and the current asteroid continues checking against the next stack element in another loop iteration. Stack top wins: the stack top is larger, the current asteroid is destroyed and the loop exits without pushing. Tie: both are equal in absolute value, both are destroyed — the stack top is popped and the current asteroid is discarded.
The win case is what makes a while loop necessary rather than a simple if statement. A single large negative asteroid can cascade through multiple positive asteroids on the stack. For example, in [2, 3, 4, -10], the -10 asteroid collides with 4 (wins), then collides with 3 (wins), then collides with 2 (wins), and finally reaches an empty stack. It has destroyed three asteroids in one cascading chain. The while loop handles this naturally — each pop reveals the next potential collision target.
The tie and lose cases both cause the current asteroid to be discarded. The difference is that a tie also pops the stack top, while a loss does not. Both immediately exit the while loop. After the loop, a boolean survived flag (or a check on whether the loop exited normally vs. via break) determines whether to push the current asteroid. A clean implementation uses a flag variable set to False when the current asteroid is destroyed in either the tie or loss case.
Cascading Destruction — One Negative Can Destroy Many Positives
A large negative asteroid can destroy multiple positive ones in sequence through cascading collisions. The while loop naturally handles this: each iteration of the loop checks the next stack top after the previous one was popped. This is why a while loop is required, not a simple if statement. For example, -100 would destroy every positive asteroid on the stack regardless of how many there are, stopping only at an empty stack or a negative stack top.
Walk-Through Examples — Three Traces Covering Win, Lose, and Tie
Example 1 — Stack top wins: input [5, 10, -5]. Process 5: stack = [5]. Process 10: stack = [5, 10]. Process -5: collision with 10 (|−5|=5 < 10), -5 destroyed; stack stays [5, 10]. Result: [5, 10]. The -5 asteroid was too small to destroy 10 and both 5 and 10 survive.
Example 2 — Tie, both destroyed: input [8, -8]. Process 8: stack = [8]. Process -8: collision with 8 (|−8|=8 == 8), both destroyed; stack = []. Result: []. Equal-size asteroids annihilate each other completely, leaving an empty result.
Example 3 — Cascading current wins: input [10, 2, -5]. Process 10: stack = [10]. Process 2: stack = [10, 2]. Process -5: collision with 2 (|−5|=5 > 2), pop 2; stack = [10]; -5 still alive. Collision with 10 (|−5|=5 < 10), -5 destroyed; stack stays [10]. Result: [10]. The -5 destroys 2 but is then destroyed by the larger 10.
- 1Trace [5, 10, -5]: push 5 → [5]; push 10 → [5,10]; -5 vs 10: lose, discard -5 → result [5,10]
- 2Trace [8, -8]: push 8 → [8]; -8 vs 8: tie, pop 8, discard -8 → stack empty → result []
- 3Trace [10, 2, -5]: push 10 → [10]; push 2 → [10,2]; -5 vs 2: win, pop 2 → [10]; -5 vs 10: lose, discard -5 → result [10]
- 4Trace [-2, -1, 1, 2]: push -2 → [-2]; push -1 → [-2,-1]; push 1 → [-2,-1,1]; push 2 → [-2,-1,1,2] → result [-2,-1,1,2]
- 5Trace [1, -2, 2, -1]: push 1 → [1]; -2 vs 1: win, pop 1 → []; -2 stack empty, push -2 → [-2]; push 2 → [-2,2]; -1 vs 2: lose, discard -1 → result [-2,2]
Code Walkthrough — Python and Java with O(n) Time and O(n) Space
Python solution using a survived flag: def asteroidCollision(asteroids): stack = []; for a in asteroids: survived = True; while survived and stack and a < 0 < stack[-1]: if stack[-1] < -a: stack.pop(); elif stack[-1] == -a: stack.pop(); survived = False; else: survived = False; if survived: stack.append(a); return stack. The condition a < 0 < stack[-1] elegantly checks both that the current asteroid is negative and the stack top is positive in one expression.
Java solution: public int[] asteroidCollision(int[] asteroids) { Deque<Integer> stack = new ArrayDeque<>(); for (int a : asteroids) { boolean survived = true; while (survived && !stack.isEmpty() && a < 0 && stack.peek() > 0) { if (stack.peek() < -a) { stack.pop(); } else if (stack.peek() == -a) { stack.pop(); survived = false; } else { survived = false; } } if (survived) stack.push(a); } int[] res = new int[stack.size()]; int i = stack.size() - 1; for (int v : stack) res[i--] = v; return res; } Note: Java Deque acts as a stack with push/pop from the front, so reverse when building the result array.
Time complexity: O(n) — each asteroid is pushed onto the stack at most once and popped at most once, so the total number of stack operations across all iterations is bounded by 2n. Space complexity: O(n) — the stack holds at most all n asteroids in the worst case (all positive or all negative, no collisions). The algorithm is optimal for this problem since every asteroid must be examined at least once.
Push the Survivor After the While Loop — Do Not Push Inside It
After the collision while loop exits, push the current asteroid only if it survived. Use a boolean survived flag initialized to True; set it to False when the current asteroid is destroyed in a tie or loss. Do not push inside the while loop — the loop is for collision resolution only. The push happens once, after the loop, when survived is still True. Forgetting this step will silently produce wrong results that are hard to debug because the stack looks correct during the loop.