Generated by Codex with GPT-5

Quick facts

Problem gist

The input describes asteroids arranged from left to right. A positive number moves right, a negative number moves left, and the absolute value is the asteroid’s size. When two asteroids meet, the smaller one disappears; if their sizes are equal, both disappear. The goal is to return the asteroids that remain, in their original left-to-right order.

Because every asteroid moves at the same speed, most pairs can never meet. Two asteroids collide only when a right-moving asteroid is somewhere to the left of a left-moving asteroid. That observation turns the problem into a local simulation instead of a time-by-time physics simulation.

Key idea

Process the asteroids from left to right while keeping a stack of survivors. Before a new asteroid arrives, the stack is already stable: none of its asteroids can collide with another survivor.

A new asteroid can disturb that stable state only when it moves left and the stack’s top asteroid moves right. Those two are heading toward each other, so compare their sizes:

  • If the stack’s top is smaller, remove it. The incoming asteroid may then collide with the new top, so continue the loop.
  • If both sizes are equal, remove the top and discard the incoming asteroid.
  • If the stack’s top is larger, discard the incoming asteroid.

If no opposing right-moving asteroid remains, append the incoming asteroid. The stack is stable again, which gives a useful invariant after every iteration.

For example, with [10, 2, -5], both positive asteroids are pushed. The -5 first destroys 2, but it must then face 10. The 10 is larger, so the final stack is [10]. This repeated comparison with the newest survivor is exactly why a stack fits the problem.

Python solution

from typing import List


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

        for incoming_asteroid in asteroids:
            self._place_asteroid(survivors, incoming_asteroid)

        return survivors

    @staticmethod
    def _place_asteroid(survivors: List[int], incoming_asteroid: int) -> None:
        """Resolve one asteroid against the already-stable survivor stack."""
        while (
            survivors
            and survivors[-1] > 0
            and incoming_asteroid < 0
        ):
            right_moving_size = survivors[-1]
            incoming_size = -incoming_asteroid

            if right_moving_size < incoming_size:
                # The incoming asteroid survives this collision and may hit
                # another right-moving asteroid farther to the left.
                survivors.pop()
                continue

            if right_moving_size == incoming_size:
                # Equal-sized asteroids destroy each other.
                survivors.pop()

            # The incoming asteroid is destroyed in both the equal-size and
            # larger-right-moving-asteroid cases.
            return

        # No collision is possible with the current top of the stack.
        survivors.append(incoming_asteroid)

The runtime is O(n), where n is the number of asteroids. Although one incoming asteroid can trigger several loop iterations, each asteroid is pushed once and popped at most once. The stack uses O(n) extra space in the worst case, and the input is left unchanged.

Why this derives naturally

A direct simulation might repeatedly scan the array for colliding neighbors, remove a pair, and start over. That is correct but can take O(n^2) time because the same surviving asteroids may be scanned many times.

The stack removes that repeated work. Once an asteroid has survived everything processed to its left, only a future left-moving asteroid can threaten it. The nearest surviving asteroid must be handled first, so the last survivor is exactly the value the algorithm needs to inspect.

The signs also rule out every other case:

  • Two positive asteroids move right together.
  • Two negative asteroids move left together.
  • A negative asteroid followed by a positive asteroid moves away from the boundary between them.
  • Only a positive survivor followed by a negative incoming asteroid moves toward that boundary.

This is why a single condition captures every possible collision and why the stack after each insertion represents the complete answer for the prefix processed so far.

Interview follow-ups

Can the algorithm use constant auxiliary space?

Yes, if mutating the input is allowed. Treat the input list itself as the stack and keep a write index for the number of current survivors. Read each asteroid once, resolve it against the value at write_index - 1, and overwrite the next stack position when it survives. Return the prefix ending at the final write index.

The collision logic and amortized proof remain the same, so the runtime is O(n). Auxiliary space becomes O(1), but the tradeoff is that the original input is destroyed and the returned result may still require a slice or a length boundary, depending on the required interface.

How would you prove that the nested loop is linear rather than quadratic?

Use aggregate analysis. Every asteroid is considered once by the outer loop and can be appended to the survivor stack at most once. A successful repeated collision removes one asteroid from that stack, and no removed asteroid can ever return. Therefore, all executions of the pop branch across the entire run total at most n.

The remaining comparison either appends or discards the incoming asteroid and ends its processing. The total work is consequently proportional to the number of pushes, pops, and discarded inputs: O(n) time despite the nested syntax.

How would you return the collisions as events as well as the final survivors?

Store a stable identifier or original index with every asteroid in the stack. Whenever the algorithm compares an incoming asteroid with the top survivor, record the two identifiers and which asteroid, if either, survives. Then perform the same pop, discard, or append operation as before.

This works because the stack simulation already visits collisions in the only order in which they can happen for the equal-speed model. There can be only O(n) destructive collision events because every event eliminates at least one asteroid, so recording them keeps the runtime at O(n) and adds O(c) output space for c reported events.

Can the asteroids be processed as a stream?

Yes. Preserve the survivor stack between chunks and feed each arriving asteroid through the same placement routine. The stack invariant depends only on the survivors of the processed prefix, not on how that prefix was divided into batches.

Processing remains O(n) overall. Memory is O(s) for s current survivors, and that bound is unavoidable in general because an all-positive stream may require every asteroid to appear in the final answer. Results can be emitted early only in special cases; for example, a leading left-moving survivor can never be reached by a future asteroid arriving to its right.

What changes if asteroids can move at different speeds?

The simple stack is no longer sufficient. A faster asteroid can catch another moving in the same direction, and the next collision depends on positions, velocities, and time rather than signs alone. Model adjacent asteroids with a doubly linked list, calculate each adjacent pair’s next collision time, and keep those candidate events in a min heap.

When the earliest valid event is removed from the heap, resolve that collision, unlink any destroyed asteroid, and calculate new events for the newly adjacent neighbors. Version numbers or active flags are needed to ignore stale heap entries created before earlier collisions changed the neighborhood. If c collisions occur, this event-driven approach typically costs O((n + c) log n) time and O(n) space. It is more general, but it gives up the original problem’s elegant linear-time shortcut.