DSA sheet · Stack · Monotonic stack pattern

Asteroid Collision

This is the next question in the monotonic stack pattern, right after Next Greater Element and Daily Temperatures. The teacher first lists every way two asteroids can meet, then writes a brute force that walks a list and deletes asteroids while stepping back, shows why it is O(n²), and finally replaces it with a stack that does the same job in O(n).

Why it matters: "move forward, but sometimes look back and cancel earlier items" is the signal for a stack. You will see the same shape in Remove K Digits, Backspace String Compare and the parentheses problems.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (stack, monotonic stack)
• Part A · Brute force: walk a list, delete, step back
• Part B · Optimal: a stack of survivors
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates. You can only touch the top plate. The plate you put on last is the one you take off first. This rule is called LIFO: Last In, First Out.

A Python list works as a stack because append and pop() both act on the right end, and both are O(1). In these notes we always draw a stack left = bottom, right = top, e.g. [5, 10] means 10 is on top.

What is a monotonic stack?

Monotonic means "always going one way". A monotonic stack is a stack where, before pushing a new item, we pop the items on top that the new item "beats". The stack then only remembers the items that are still useful for the future.

In Next Greater Element we popped smaller numbers because a bigger number had arrived and they would never be anyone's answer again. Here the idea is the same, but the "beating" is a collision: a big left-moving asteroid destroys the smaller right-moving asteroids at the top of the stack, one by one, until it hits something it can't beat.

Part A · Brute force: walk a list, delete, step back

LeetCode 735

1The question in simple words

You get an array asteroids. Each number is one asteroid in a row in space. Its position in the array is its position in the row.

• The size of an asteroid is the number without its sign (its absolute value). −5 and 5 have the same size, 5.
• The sign is its direction: positive → moving right, negative ← moving left.
• All asteroids move at the same speed. The number is the size (mass), not the speed. The teacher stresses this because it's easy to misread.

When two asteroids meet, the smaller one explodes. If they are the same size, both explode. Return what is left after all collisions, in order.

  asteroids = [ 5, 10, -5 ]

     5 →     10 →    ← 5          (-5 is size 5, moving left)
                10 meets -5: 10 is bigger, -5 explodes
  answer    = [ 5, 10 ]

2What the constraints tell us

• 2 ≤ n ≤ 10⁴ → at least two asteroids, so no empty-input case. And n = 10⁴ means an O(n²) solution does about 10⁸ steps, which is at the edge of TLE (Time Limit Exceeded). That's the hint that the brute force will be slow and we must find something closer to O(n).
• −1000 ≤ value ≤ 1000, and no value is 0 → tiny numbers. The teacher's rule of thumb: an int is safe up to around 10⁹; beyond that you'd need a bigger type. Here we're far below that (and in Python ints never overflow anyway).

3Intuition: when can two asteroids actually meet?

Before writing any code, the teacher lists all four direction pairs for two neighbours A (left one) and B (right one):

A collision happens only when the left one is positive and the right one is negative. Everything else is safe.

4Building the logic from examples

The three outcomes of a collision

Once we know A > 0 and B < 0, there are three ways it can end. The teacher shows one example for each:

Walking with two neighbours, i and i+1

One asteroid alone can't tell us anything; we need a pair. So we keep an index i and look at a = lst[i] and b = lst[i+1].

• If they can't collide (not "a positive, b negative") → just move on: i += 1.
• Case 1, a > −b (B is smaller): delete B. Keep i where it is, because the new neighbour at i+1 might also be a left-mover heading for A.
• Case 2, a < −b (A is smaller): delete A. Now B has moved into position i and keeps flying left. It may hit the asteroid before it too. So we must step back: i -= 1.
• Case 3, a == −b: delete both. The asteroid before them and the one after them are now neighbours, so again step back.

Why stepping back is needed: her −15 example

  [ 5, 10, -15 ]
          i  i+1         10 vs -15 → 10 explodes
  [ 5, -15 ]             -15 is still flying left!
    i  i+1               step back: 5 vs -15 → 5 explodes
  [ -15 ]                answer

If we only moved forward, we'd stop at [5, -15], which is wrong: 5 and −15 are still flying towards each other.

Same thing for "both explode": in [5, 10, -10, -10], 10 and −10 destroy each other, leaving [5, -10]. Now 5 and the second −10 are neighbours and must be compared, so i has to point at 5 again.

5Approach steps

1. Copy the array into a list we can delete from. Set i = 0.
2. While i is before the last index: let a = lst[i], b = lst[i+1].
3. If a > 0 and b < 0 (they collide):
   • a bigger → delete b (i stays).
   • b bigger → delete a, then step back if i > 0.
   • same size → delete both, then step back if i > 0.
4. Otherwise → i += 1.
5. Return the list.

6Code (Python)

class Solution:
    def asteroidCollision(self, asteroids):
        lst = list(asteroids)            # a list we can delete from
        i = 0
        while i < len(lst) - 1:         # we read i and i+1
            a, b = lst[i], lst[i + 1]
            if a > 0 and b < 0:         # only this pair can collide
                if a > -b:               # right-mover is bigger
                    lst.pop(i + 1)       # b explodes, i stays
                elif a < -b:             # left-mover is bigger
                    lst.pop(i)           # a explodes
                    if i > 0:
                        i -= 1           # b may hit the one before
                else:                    # same size
                    lst.pop(i + 1)       # both explode
                    lst.pop(i)
                    if i > 0:
                        i -= 1           # new neighbours meet
            else:
                i += 1                   # no collision, move on
        return lst

7Code line by line

8Dry run: [5, 10, −15, 3]

9Complexity & remember

• Time O(n²). It looks like one loop, so you might say O(n). But i keeps going back and re-checking pairs it already passed, which makes it behave like a loop inside a loop. Also, each delete from the middle of a list shifts all later items, which is another O(n) each time. With n = 10⁴ that's up to about 10⁸ steps.
• Space O(n) for the list copy.

The teacher submits it: it is accepted but very slow. So we optimise.

Part B · Optimal: a stack of survivors

1The question (same as Part A)

Same input, same output. We only change how we look back.

2What the constraints tell us

n up to 10⁴ and the brute force was slow → aim for O(n): every asteroid should be handled a constant number of times.

3Intuition: why a stack?

In the brute force, every time a left-mover won, we walked backwards to the asteroid just before it, then the one before that… always the most recent survivor first. The teacher connects this to Next Greater / Next Smaller Element: whenever you move ahead and then have to come back to check earlier values, use a stack.

So we keep a stack of survivors so far (left = bottom, right = top). When a new asteroid arrives, it can only crash into the top of the stack, because that's its nearest surviving neighbour. At the end, the stack is the answer.

What does the stack remember? All asteroids that are still alive, in order. Any left-movers in it are already safe forever (nothing on their left is coming at them). Any right-movers on top are "waiting": a future left-mover might still hit them.

4Building the logic: pop or don't push?

Take the new asteroid a. A collision is possible only if the stack is not empty, a < 0 (moving left) and top > 0 (moving right). Then:

The key thinking: "pop" means remove a survivor that's already in the stack; "don't push" means the new asteroid itself explodes. Whatever stays in the stack at the end is the answer.

Rule 1: a while loop to pop all smaller right-movers

while st and a < 0 and st[-1] > 0 and st[-1] < -a: st.pop()

Why while and not if? Her example: stack [5, 10], new asteroid −15. It destroys 10, and then it's still flying and also destroys 5. One if would stop after 10.

Rule 2: after the loop, does the new asteroid survive?

If the loop stopped and there is still a collision (stack not empty, a < 0, top > 0), then the top is not smaller than a (otherwise the loop would have popped it). So only two possibilities are left: the top is equal or bigger. In both, a does not survive, so we don't push it. And if they're equal, the top also explodes → pop it.

If there is no collision at all → push a. That's the else.

5Approach steps

1. Make an empty stack.
2. For each asteroid a, left to right:
3. While the stack isn't empty, a < 0, top > 0 and top < −a → pop (the top explodes).
4. If the stack isn't empty, a < 0 and top > 0 → a explodes (don't push). If top == −a, pop the top too.
5. Else → push a.
6. Return the stack (bottom to top is the left-to-right order).

6Code (Python)

class Solution:
    def asteroidCollision(self, asteroids):
        st = []                                   # survivors so far
        for a in asteroids:
            # a (moving left) destroys every smaller right-mover on top
            while st and a < 0 and st[-1] > 0 and st[-1] < -a:
                st.pop()
            if st and a < 0 and st[-1] > 0:     # still a collision
                if st[-1] == -a:                  # same size: both go
                    st.pop()
                # top is equal or bigger: a explodes, don't push
            else:
                st.append(a)                      # a survives (for now)
        return st

7Code line by line

8Dry run: [−2, 5, 10, −4, −10, −15, 3]

This one example hits every case: a left-mover at the start, "top bigger", "equal", "pop many", and two left-movers side by side.

The top is drawn in red. At i = 5, without the st[-1] > 0 check in Rule 2, −15 would wrongly be thrown away because the top (−2) is negative.

The teacher's own example, [5, 10, -5]: push 5, push 10, then −5 meets top 10, which is bigger → −5 isn't pushed → answer [5, 10].

9Complexity & remember

• Time O(n). There's a while inside a for, which looks nested, but it isn't: the while loop only pops, and each asteroid is pushed at most once, so it can be popped at most once. Over the whole run there are at most n pushes and n pops: O(n) + O(n) = O(2n) = O(n). (In Java, copying the stack into the answer array is one more O(n).)
• Space O(n): the stack can hold every asteroid, e.g. when all move the same way.

Part C · Revision page

s = Solution()
print(s.asteroidCollision([5, 10, -5]))                  # [5, 10]
print(s.asteroidCollision([8, -8]))                      # []
print(s.asteroidCollision([10, 2, -5]))                  # [10]
print(s.asteroidCollision([5, 10, -15, 3]))              # [-15, 3]
print(s.asteroidCollision([-2, 5, 10, -4, -10, -15, 3])) # [-2, -15, 3]
print(s.asteroidCollision([-5, 10, -5]))                 # [-5, 10]

Based on this video: Asteroid Collision | Stack