Leetcode Link

We can use a stack to solve this problem.

From the problem description, the planets move at the same speed, so we only need to consider their direction and size.
Whether two planets will collide and the result of the collision can be divided into three cases:

  1. asteroids = [5, 10] or asteroids = [-5, -10]

    • Both planets move in the same direction, so no collision occurs.

  2. asteroids = [-5, 10]

    • The two planets move in different directions but will not collide.

  3. asteroids = [5, -10]

    • The two planets move in opposite directions and will collide.

Collisions can be further divided into two outcomes:

  1. Different sizes: The larger planet will remain.
    Example: asteroids = [5, -10] → asteroids = [-10]

  2. Same size: Both planets will disappear.
    Example: asteroids = [8, -8] → asteroids = []

Thus, we only need to focus on cases where “two planets move in opposite directions and collide.”

We iterate through each planet, add it to the stack, and use the stack to determine whether the planet should remain or be removed based on the conditions above.

Here’s the solution in Python: 

class Solution(object):
    def asteroidCollision(self, asteroids):
        """
        :type asteroids: List[int]
        :rtype: List[int]
        """
        stack = []
        for star in asteroids:
            while stack and star < 0 and stack[-1] > 0:
                if abs(star) > abs(stack[-1]):
                    stack.pop()
                    continue
                elif abs(star) == abs(stack[-1]):
                    stack.pop()
                break
            else:
                stack.append(star)
        return stack