# LeetCode 735: Asteroid Collision

## Problem Restatement

We are given an integer array `asteroids`.

Each integer represents one asteroid.

The absolute value is the asteroid size.

The sign is its direction:

| Value | Direction |
|---|---|
| Positive | Moving right |
| Negative | Moving left |

All asteroids move at the same speed.

When two asteroids collide:

| Case | Result |
|---|---|
| Smaller asteroid | Explodes |
| Same size | Both explode |
| Same direction | They never collide |

We need to return the final state after all collisions. A collision only happens when a right-moving asteroid is before a left-moving asteroid. The official problem defines positive values as moving right, negative values as moving left, and asks for the state after all collisions.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of integers `asteroids` |
| Output | A list of surviving asteroids |
| Size | `abs(asteroids[i])` |
| Direction | Sign of `asteroids[i]` |
| Important case | Only `positive` before `negative` can collide |

Example function shape:

```python
def asteroidCollision(asteroids: list[int]) -> list[int]:
    ...
```

## Examples

### Example 1

```python
asteroids = [5, 10, -5]
```

The asteroid `10` moves right.

The asteroid `-5` moves left.

They collide.

Since `10` is larger than `5`, `-5` explodes.

The result is:

```python
[5, 10]
```

### Example 2

```python
asteroids = [8, -8]
```

The two asteroids collide.

They have the same size, so both explode.

The result is:

```python
[]
```

### Example 3

```python
asteroids = [10, 2, -5]
```

First, `2` and `-5` collide.

`-5` has size `5`, so it destroys `2`.

Now `10` and `-5` collide.

`10` is larger, so `-5` explodes.

The result is:

```python
[10]
```

### Example 4

```python
asteroids = [-2, -1, 1, 2]
```

The negative asteroids move left.

The positive asteroids move right.

They are moving away from each other, so no collision happens.

The result is:

```python
[-2, -1, 1, 2]
```

## First Thought: Simulate Collisions

We can process asteroids from left to right.

When we see an asteroid, it may collide only with earlier asteroids that are still alive.

More specifically, a collision can happen only when:

```python
previous asteroid > 0
current asteroid < 0
```

That means the previous asteroid is moving right and the current asteroid is moving left.

The closest previous asteroid matters first. If it explodes, the current asteroid may continue and collide with the next previous asteroid.

This last-survivor-first-collision behavior suggests a stack.

## Key Insight

Use a stack to store asteroids that have survived so far.

For each new asteroid `x`:

- If `x` is moving right, push it.
- If `x` is moving left, it may collide with right-moving asteroids at the top of the stack.
- While the top of the stack is positive and `x` is negative, resolve the collision.

There are three collision outcomes:

| Condition | Result |
|---|---|
| `abs(x) > stack[-1]` | Top asteroid explodes, continue checking |
| `abs(x) == stack[-1]` | Both explode |
| `abs(x) < stack[-1]` | Current asteroid explodes |

If the current asteroid survives all possible collisions, push it onto the stack.

## Algorithm

Create an empty stack.

For each asteroid `x` in `asteroids`:

1. Assume `x` is alive.
2. While `x` is alive, the stack is not empty, `stack[-1] > 0`, and `x < 0`:
   - If `stack[-1] < -x`, pop the stack.
   - Else if `stack[-1] == -x`, pop the stack and mark `x` as destroyed.
   - Else mark `x` as destroyed.
3. If `x` is still alive, append it to the stack.
4. Return the stack.

## Correctness

The stack stores exactly the surviving asteroids among the prefix already processed, in their original order.

When the next asteroid moves right, it cannot collide with any previous asteroid immediately. Any previous right-moving asteroid moves in the same direction, and any previous left-moving asteroid is moving away from it. So pushing it is correct.

When the next asteroid moves left, it can collide only with previous right-moving asteroids. Among those, the nearest surviving one is at the top of the stack. Therefore resolving collision against `stack[-1]` first is correct.

If the top asteroid is smaller, it explodes, and the current asteroid may continue left into the next surviving asteroid. Popping and continuing is correct.

If both have equal size, both explode. Popping the top and discarding the current asteroid is correct.

If the top asteroid is larger, the current asteroid explodes. Keeping the stack unchanged is correct.

After all possible collisions for the current asteroid are resolved, if it remains alive, no previous surviving asteroid can collide with it. Therefore appending it preserves the stack invariant.

After every asteroid is processed, the stack contains exactly the final surviving asteroids.

## Complexity

Let `n = len(asteroids)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each asteroid is pushed once and popped at most once |
| Space | `O(n)` | The stack may store all asteroids |

Even though there is a nested `while` loop, the total number of pops across the whole algorithm is at most `n`.

## Implementation

```python
class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        stack = []

        for x in asteroids:
            alive = True

            while alive and stack and stack[-1] > 0 and x < 0:
                top = stack[-1]

                if top < -x:
                    stack.pop()
                elif top == -x:
                    stack.pop()
                    alive = False
                else:
                    alive = False

            if alive:
                stack.append(x)

        return stack
```

## Code Explanation

We use `stack` to store the asteroids that are still alive:

```python
stack = []
```

For each asteroid, we track whether it survives:

```python
alive = True
```

The collision loop runs only in the one possible collision direction:

```python
while alive and stack and stack[-1] > 0 and x < 0:
```

If the stack top is smaller:

```python
if top < -x:
    stack.pop()
```

the top asteroid explodes, and the current asteroid keeps moving left.

If both sizes are equal:

```python
elif top == -x:
    stack.pop()
    alive = False
```

both explode.

If the stack top is larger:

```python
else:
    alive = False
```

the current asteroid explodes.

After the loop, a surviving asteroid is stored:

```python
if alive:
    stack.append(x)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.asteroidCollision([5, 10, -5]) == [5, 10]
    assert s.asteroidCollision([8, -8]) == []
    assert s.asteroidCollision([10, 2, -5]) == [10]
    assert s.asteroidCollision([-2, -1, 1, 2]) == [-2, -1, 1, 2]

    assert s.asteroidCollision([1, -2]) == [-2]
    assert s.asteroidCollision([2, -1]) == [2]
    assert s.asteroidCollision([1, 2, 3, -6]) == [-6]
    assert s.asteroidCollision([-2, 2, -2, -1]) == [-2, -1]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[5, 10, -5]` | Current left-moving asteroid is destroyed |
| `[8, -8]` | Equal sizes destroy both |
| `[10, 2, -5]` | One asteroid causes multiple collisions |
| `[-2, -1, 1, 2]` | No collision because asteroids move away |
| `[1, -2]` | Current asteroid destroys stack top |
| `[2, -1]` | Stack top destroys current asteroid |
| `[1, 2, 3, -6]` | Current asteroid destroys many asteroids |
| `[-2, 2, -2, -1]` | Existing left movers remain safe |