https://leetcode.com/problems/asteroid-collision

Let us traverse our asteroids from left to right and keep in stack so-called stable set: it means, that the will be no collisions anymore in our stack. What happen, when we add new asteroid: there can be 3 main cases:

  1. If we have in stack [....7] and we add -3, then this last asteroid is destroyed, which is the last one: so if we have stack[-1] + stack[-2] > 0, then we pop the last element fro our stack.
  2. If we have in stack [....3] and we add -7, then asteroid with weight 3 is destroyed: so we need to pop one elements before last from our stack.
  3. If we have in stack [....3] and we add -3, then both these two asteroids is destroyed: we remove two last elements from our stack.

Complexity: time complexity is O(n), because for each asteroid, we can either put or remove it from stack once (not also that we sometimes remove not last element, but one before last, but complexity of this operation is still O(1). Space complexity is also can be potentially as big as O(n).

class Solution:
    def asteroidCollision(self, asteroids):
        stack = []
        for ast in asteroids:
            stack.append(ast)
            while len(stack) > 1 and stack[-1] < 0 and stack[-2] > 0:
                if stack[-1] + stack[-2] < 0: stack.pop(-2)
                elif stack[-1] + stack[-2] > 0: stack.pop()
                else:
                    stack.pop(); stack.pop()
                    break
        
        return stack

If you like the solution, you can upvote it on leetcode discussion section: Problem 0735