Asteroid Collision — LeetCode 735 Python Solution

The 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.

Example

Input

asteroids = [5,10,-5]

Output

[5,10]

Explanation

The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Python solution

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stk = []
        for x in asteroids:
            if x > 0:
                stk.append(x)
            else:
                while stk and stk[-1] > 0 and stk[-1] < -x:
                    stk.pop()
                if stk and stk[-1] == -x:
                    stk.pop()
                elif not stk or stk[-1] < 0:
                    stk.append(x)
        return stk

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 735. Asteroid Collision is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems