subject

735. Planetary collision

Medium difficulty 342 Switch to English to receive dynamic feedback

Given an array of integers asteroids, Represents planets on the same line .

For each element in the array , Its absolute value represents the size of the planet , Positive and negative indicate the direction of movement of the planet （ Positive means moving to the right , Negative means moving to the left ）. Every planet moves at the same speed .

Find all the planets left after the collision . Collision rules ： The two planets collide with each other , Smaller planets will explode . If two planets are the same size , Then both planets will explode . Two planets moving in the same direction , There will never be a collision .

Example 1：

 Input ：asteroids = [5,10,-5]
 Output ：[5,10]
 explain ：10  and  -5  After the collision, only  10 . 5  and  10  There will never be a collision .

Example 2：

 Input ：asteroids = [8,-8]
 Output ：[]
 explain ：8  and  -8  After the collision , Both exploded .

Example 3：

 Input ：asteroids = [10,2,-5]
 Output ：[10]
 explain ：2  and  -5  After the collision, there are  -5 .10  and  -5  After the collision, there are  10 .

Tips ：

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

Ideas

• Use stack to simulate collision process
• Traverse the array from left to right , New planets constantly collide with the planets in the stack to the right until they die or collide with all the planets in the stack

Code

from collections import deque
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack = deque()
        for planet in asteroids:
            alive = True
            while alive and stack and stack[-1]>0 and planet<0:
                alive = stack[-1] < -planet
                if stack[-1] <= -planet: stack.pop()
            if alive: stack.append(planet)
        return list(stack)

Complexity

• Time complexity ：$O(n)$
• Spatial complexity ：$O(n)$