Skip to main content
DSA patterns

Asteroid Collision

mediumStack and queue

Problem statement

A row of asteroids is given as a list of non-zero integers. The absolute value is an asteroid's size and the sign is its direction: positive moves right, negative moves left. All asteroids move at the same speed.

When a right-moving asteroid meets a left-moving one, the smaller one explodes. If they are the same size, both explode. Asteroids moving in the same direction never meet, and a left-moving asteroid to the left of a right-moving one moves away from it.

Return the asteroids that are left once no more collisions can happen, in their original left-to-right order.

Examples

Example 1

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

Output: [10]

Explanation: -5 hits 2 first, and 2 explodes because it is smaller. Then -5 hits 10, and -5 explodes. Only 10 is left.

Example 2

Input: asteroids = [8, -8]

Output: []

Explanation: The two asteroids have the same size, so both explode and nothing is left.

Hints

Hint 1: Only one pattern collides: a positive value immediately followed by a negative value. Every other neighbouring pair moves apart or in the same direction.

Approach

Optimal: Stack

Intuition

Read the asteroids from left to right and keep the survivors so far in a stack. Survivors to the left of the current point are in a fixed order, and the only one a new asteroid can hit is the last one, the top of the stack. A new right-mover can never collide with anything on the left, so it is just pushed. A new left-mover fights the top while the top is a right-mover. This is faster than the brute force because each asteroid is handled once and no scan restarts.

Steps

  1. For each asteroid rock, assume it is alive.
  2. While rock is negative, the stack is not empty and the top is positive, they collide:
    • top is smaller: pop it and keep checking with the next top;
    • top is the same size: pop it, and rock is also gone;
    • top is bigger: rock is gone.
  3. If rock is still alive after the loop, push it.
  4. At the end, the stack read from bottom to top is the answer.

Dry run

asteroids = [10, 2, -5]

rock stack before what happens stack after
10 [] right-mover, push [10]
2 [10] right-mover, push [10, 2]
-5 [10, 2] top 2 is smaller, pop; top 10 is bigger, -5 explodes [10]

Edge cases: [8, -8] pops 8 and destroys -8, leaving []. A negative asteroid with an empty stack, as in [-2, 1], is pushed, because nothing is on its left.

Complexity

Time O(n) - Each asteroid is pushed onto the stack at most once. It is also popped at most once, either by a bigger left-mover or in a tie. So the total number of stack operations is at most 2n, even though there is a `while` loop inside the `for` loop.

Space O(n) - In the worst case nobody collides, for example when every asteroid moves the same way, so all n stay on the stack. The stack is also the answer, so we do not build a second list. That is why the space is O(n).

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []   # survivors so far, left to right
        for rock in asteroids:
            alive = True
            while alive and rock < 0 and stack and stack[-1] > 0:
                if stack[-1] < -rock:      # top is smaller: it explodes, keep checking
                    stack.pop()
                elif stack[-1] == -rock:   # same size: both explode
                    stack.pop()
                    alive = False
                else:                      # top is bigger: incoming one explodes
                    alive = False
            if alive:
                stack.append(rock)
        return stack


if __name__ == "__main__":
    print(Solution().asteroidCollision([10, 2, -5]))
    print(Solution().asteroidCollision([8, -8]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: asteroids move left or right (sign is direction), and they collide only when a right-mover meets a left-mover
  • Idea: stack: a negative asteroid pops smaller positive ones on top, both vanish if equal, and it is added only if nothing bigger blocks it
  • Cost: O(n) time, O(n) space
  • Trap: equal sizes destroy both, and a left-mover with an empty stack or a left-mover on top never collides

Interview follow-ups

  • Return how many collisions happened as well as the survivors.

    Keep a counter next to the stack. Each time the incoming left-moving asteroid meets a right-moving top, add one to the counter, whatever the outcome: the top is destroyed, both are destroyed, or the incoming one is destroyed. Return the survivors and the counter together. Equal sizes are one collision, not two, because both asteroids explode in the same meeting. Time and space stay O(n), and the count can never exceed n, because every collision destroys at least one asteroid.

  • What changes if asteroids can have different speeds?

    The stack idea stops working, because a faster asteroid can now catch up with a slower one moving in the same direction, so the order of meetings is no longer simply left to right. You have to simulate by time instead. Put the asteroids in a doubly linked list, and for each neighbouring pair that will meet, compute the meeting time from the gap and the speeds. Keep these times in a min-heap. Repeatedly take the earliest meeting, resolve it, remove the destroyed asteroids from the list, and push the new meeting time for the pair that became neighbours. Skip heap entries that involve an asteroid already destroyed. This costs O(n log n), and you must decide how to treat several meetings at exactly the same time.

  • The asteroids arrive one at a time. How do you report the survivors after each new one?

    The stack is already the running answer, so nothing changes. For each arriving asteroid, run the collision loop against the top of the stack and push it if it survives. The stack contents, read from bottom to top, are the survivors at that moment. Each asteroid is pushed and popped at most once, so every arrival costs O(1) amortized and the memory is O(n).

Frequently asked questions

The -2 moves left and the 1 moves right, so they move apart. A collision needs a positive value on the left and a negative value on the right. In the stack code this is why the loop needs both rock < 0 and a positive top.

One large left-moving asteroid can destroy several smaller right-movers in a row, as in [3, 5, -8]. It has to keep going until it is stopped or the stack runs out of right-movers. A single if would stop after the first collision and give the wrong answer.

They are pushed onto the stack, because there is no right-mover before them. They stay in the answer forever, since nothing on their left can ever catch them. This is why the answer can start with several negative numbers.

It is a clean example of resolving events against the most recent unresolved item, which is the same shape as matching open and close events in a log or cancelling a queued deploy with a later rollback. The stack of "still open" items is the common tool for these problems.