class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for asteroid in asteroids:
# If stack is not empty and asteroid towards left, original asteroid towards right
while stack and asteroid < 0 < stack[-1]:
if stack[-1] < -asteroid:
stack.pop()
continue
elif stack[-1] == -asteroid:
stack.pop()
break
else:
stack.append(asteroid)
My own solution:
from typing import List
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
ans = [asteroids[0]]
for asteroid in asteroids[1:]:
finished = False
# if there is no asteroid in ans, directly add new asteroid into
if not ans:
ans.append(asteroid)
finished = True
while not finished:
original_asteroid = ans[-1]
# has different direction
if asteroid * original_asteroid < 0:
# asteroid towards right, the orignal towards left, no collision
if original_asteroid < 0 and asteroid > 0:
ans.append(asteroid)
finished = True
else:
if abs(asteroid) == abs(original_asteroid): # two asteroids will disappear
ans.pop()
finished = True
elif abs(asteroid) > abs(original_asteroid): # new asteroid will replace the original
ans.pop()
if not ans:
ans.append(asteroid)
finished = True
else: # original asteroid will remain
finished = True
else: # has same direction
ans.append(asteroid)
finished = True
return ans
solution = Solution()
solution.asteroidCollision([1,-1,-2,-2])