> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Asteroid Collision Python Solution with Tests

> Tested Python solution for LeetCode 735 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 735, Medium. Topics: Array, Stack, Simulation. [View on LeetCode](https://leetcode.com/problems/asteroid-collision/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 735   # by problem number
lcpy gen -s asteroid_collision   # by problem name
```

## Problem

We are given an array `asteroids` of integers representing asteroids in a row. The indices of the asteroid in the array represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction, or two moving away from each other, will never meet.

### Examples

```
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
```

```
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
```

```
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
```

```
Input: asteroids = [3,5,-6,2,-1,4]
Output: [-6,2,4]
Explanation: The asteroid -6 makes the asteroid 3 and 5 explode, and then continues going left. On the other side, the asteroid 2 destroys -1. Since 2 and 4 are both moving right, they never collide.
```

### Constraints

* 2 \<= asteroids.length \<= 10^4
* -1000 \<= asteroids\[i] \<= 1000
* `asteroids[i] != 0`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/asteroid_collision/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/asteroid_collision/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(n)
    def asteroid_collision(self, asteroids: list[int]) -> list[int]:
        stack: list[int] = []
        for asteroid in asteroids:
            while stack and stack[-1] > 0 and asteroid < 0:
                collision = stack[-1] + asteroid
                if collision < 0:
                    stack.pop()
                elif collision > 0:
                    break
                else:
                    stack.pop()
                    break
            else:
                stack.append(asteroid)
        return stack
```

## Complexity

| Time | Space |
| ---- | ----- |
| O(n) | O(n)  |

## Tags

[Grind](/catalog/grind), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).