735. Asteroid Collision

Problem Statement

link: LeetCode.cn LeetCode We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example:

Input: asteroids = [5,10,-5] Output: [5,10]

Input: asteroids = [8,-8] Output: []

Input: asteroids = [10,2,-5] Output: [10]

Solution Approach

The solution employs a stack to simulate asteroid collisions, ensuring that asteroids moving in opposite directions collide correctly, with the smaller one exploding.

Algorithm

1. Iterate through each asteroid in the given array.
2. If the stack is empty or the current asteroid is moving right (positive) or the top of the stack is also moving right, push the asteroid onto the stack.
3. Otherwise, continuously compare the current asteroid with the top of the stack until they collide, with smaller asteroids exploding and larger ones remaining on the stack.

Implement

    class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        # stack  store right direction
        # stack[-1] v.s. abs(a)
        st = []
        for aster in asteroids:
            alive = True
            while alive and aster < 0 and st and st[-1] > 0:
                alive = st[-1] < -aster
                if st[-1] <= -aster:
                    st.pop()
            if alive:
                st.append(aster)
        return st
  

    
    

Twitter  facebook  Email