< Back




735. Asteroid Collision

Fun problem. Given some asteroids, their sign tells what direction they're going. If the signs don't
match, and one asteroid is bigger than the other, the smaller one explodes - vice versa. If they're
the same size, different direction, they both explode.

We have to return the number of remaining asteroids after all collisions are resolved. We can solve
this using a stack - kinda monotonically. We essentially keep processing the asteroids with
different signs at the top of the stack vs the current asteroid until one of the explodes. We do
some calculations to find out which one remains.

The solution is as follows:


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

          for asteroid in asteroids:
              stack.append(asteroid)
              n += 1

              while n > 1 and stack[-1] < 0 and stack[-2] > 0:
                  x, y = stack.pop(), stack.pop()

                  if abs(y) < abs(x):
                      stack.append(x)
                      n += 1
                  elif abs(y) > abs(x):
                      stack.append(y)
                      n += 1

                  n -= 2

          return stack


_ Time Complexity:

  O(n) - We process all asteroids once.

_ Space Complexity:

  O(n) - We maintain a stack of remaining asteroids post-collision.