leetcode-stack

735. Asteroid Collision.py

class Solution:
    """
    So, may i know what will hapeen when a new asteroid is added on the right?
    Ask interview to provide more examples to discuss such as [-2,-1,1,2]
    Does return order matter?
    
    Thought Process:
        Brute Force/ Naive way:
            we iterate
        Stack:
            We use a stack to maintain all survived asteroids to the left of asteroids[i].
            And top of stack should be closest survived asteroid to the left of arr[i]
            We travser all asteroids forward.
    """
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        """
        Naive way
        T:O(n^2)
        """
        for i in range(len(asteroids)):
            if asteroids[i] < 0:
                # we iterate all asteroids on the left side of arr[i]
                for j in range(i - 1 , - 1 , -1):
                    if asteroids[j] > 0:
                        if abs(asteroids[j]) > abs(asteroids[i]):
                            # we set 0 mean we will remove them because asteroids[i] != 0(constraint)
                            asteroids[i] = 0
                        elif abs(asteroids[j]) < abs(asteroids[i]):
                            asteroids[j] = 0
                        else:
                            asteroids[i] = asteroids[j] = 0
        return [i for i in asteroids if i != 0]
    
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        """
        stack
        T:O(n) because our stack pushes and pops each asteroid at most once.
        S:O(n)
        """
        # we use a stack to maintain all survived asteroids to the left of asteroids[i].
        stack = collections.deque([])
        for asteroid in asteroids:
            if asteroid > 0:
                stack.append(asteroid)
            else:
                #asteroid 小於0才需要考慮會有相撞的可能
                while len(stack) != 0 and stack[-1] > 0 and abs(asteroid) > abs(stack[-1]):
                    # peek of stack/ top of stack will be destroyed
                    stack.pop()
                if len(stack) != 0 and -asteroid == stack[-1]:
                    # top of stack and current asteroid both will be destroyed
                    stack.pop()
                elif len(stack) == 0 or stack[-1] < 0:
                    # 這種情況不會有碰撞發生的可能性
                    stack.append(asteroid)
        # stack:最後stack裡面剩下的就是還存活的asteroid
        n = len(stack)
        res = [0] * n
        # traverse backwards
        for i in range(n-1, -1, -1):
            res[i] = stack.pop()
        return res