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 1:

Input: 
asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: 
The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.



Example 2:

Input: 
asteroids = [8, -8]
Output: []
Explanation: 
The 8 and -8 collide exploding each other.



Example 3:

Input: 
asteroids = [10, 2, -5]
Output: [10]
Explanation: 
The 2 and -5 collide resulting in -5.  The 10 and -5 collide resulting in 10.



Example 4:

Input: 
asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation: 
The -2 and -1 are moving left, while the 1 and 2 are moving right.
Asteroids moving the same direction never meet, so no asteroids will meet each other.



Note:
The length of asteroids will be at most 10000.
Each asteroid will be a non-zero integer in the range [-1000, 1000]..

Difficulty: interview

Starter code:

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        

Solutions:
class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         l=len(asteroids)
         if l<2:
             return asteroids
         ans=[]
         stack=[]
         for a in asteroids:
             if a>0:
                 stack.append(a)
             else:
                 a=-a
                 equal_flag=False
                 while stack:
                     cur=stack.pop()                  
                     if cur==a:
                         equal_flag=True
                         break
                     elif cur>a:
                         stack.append(cur)
                         break              
                 if equal_flag:
                     continue            
                 if not stack:
                     ans.append(-a)
         return ans+stack
             


class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         st, res = [], []
         for ast in asteroids:
             if ast > 0:
                 st.append(ast)
                 continue
             elif not st:
                 res.append(ast)
                 continue
             flag = True
             while st:
                 if abs(ast) < st[-1]:
                     flag = False
                     break
                 ast1 = st.pop()
                 if abs(ast) == ast1:
                     flag = False
                     break
             if flag:
                 res.append(ast)
         return res + st
                     


class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         #O(N) time and O(N) space
         #stack solution        
         ans = []
         for new in asteroids:
             while True:
                 if ans and new < 0 < ans[-1]:
                     if ans[-1] < abs(new):
                         ans.pop()
                         continue
                     elif ans[-1] == abs(new):
                         ans.pop()
                     break
                 else:
                     ans.append(new)
                     break
         return ans

class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         stack = []
         for a in asteroids:
             if a >= 0 or a < 0 and (not stack or stack[-1] < 0):
                 stack.append(a)
             else:
                 while a < 0 and stack and stack[-1] > 0:
                     last = stack.pop() # last > 0
                     a = a if -a > last else last if -a < last else 0
                 if a != 0:
                     stack.append(a)
         
         return stack

#
 # [735] Asteroid Collision
 #
 # https://leetcode.com/problems/asteroid-collision/description/
 #
 # algorithms
 # Medium (37.15%)
 # Total Accepted:    6.6K
 # Total Submissions: 17.7K
 # Testcase Example:  '[5,10,-5]'
 #
 # 
 # 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 1:
 # 
 # Input: 
 # asteroids = [5, 10, -5]
 # Output: [5, 10]
 # Explanation: 
 # The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.
 # 
 # 
 # 
 # Example 2:
 # 
 # Input: 
 # asteroids = [8, -8]
 # Output: []
 # Explanation: 
 # The 8 and -8 collide exploding each other.
 # 
 # 
 # 
 # Example 3:
 # 
 # Input: 
 # asteroids = [10, 2, -5]
 # Output: [10]
 # Explanation: 
 # The 2 and -5 collide resulting in -5.  The 10 and -5 collide resulting in
 # 10.
 # 
 # 
 # 
 # Example 4:
 # 
 # Input: 
 # asteroids = [-2, -1, 1, 2]
 # Output: [-2, -1, 1, 2]
 # Explanation: 
 # The -2 and -1 are moving left, while the 1 and 2 are moving right.
 # Asteroids moving the same direction never meet, so no asteroids will meet
 # each other.
 # 
 # 
 # 
 # Note:
 # The length of asteroids will be at most 10000.
 # Each asteroid will be a non-zero integer in the range [-1000, 1000]..
 # 
 #
 class Solution:
     def asteroidCollision(self, asteroids):
         stack = []
         for a in asteroids:
             if a == 0:
                 continue
             inserted = False
             while not inserted:
                 if len(stack) == 0 or a > 0 or (stack[-1]*a > 0):
                     stack.append(a)
                     inserted = True
                 elif stack[-1] > 0 and a < 0:
                     if stack[-1] > abs(a):
                         inserted = True
                     elif stack[-1] < abs(a):
                         stack.pop()
                     else:
                         stack.pop()
                         inserted = True
         return stack
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         


class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         if not asteroids:
             return asteroids
 
         remaining = []
         for item in asteroids:
                             
             itemSign, itemVal = self.getItemDetails(item)
             shouldAppend = False
 
             while True:
                 if not remaining:
                     shouldAppend = True
                     break
                 
                 topSign, topVal = self.getItemDetails(remaining[-1])
 
                 if not (topSign and not itemSign):
                     shouldAppend = True
                     break
 
                 if topVal > itemVal:
                     break
                 elif topVal == itemVal:
                     remaining.pop()
                     break
                 else:
                     remaining.pop()
                                                                     
             if shouldAppend:
                 remaining.append(item)
 
         return remaining
 
     def getItemDetails(self, val):
         return val > 0, abs(val)

class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         
         ret = []
         
         for val in asteroids:
             
             append_flag = True
             
             while len(ret) > 0:
                 
                 # both neg or pos
                 if val * ret[-1] > 0:
                     break
                     
                 if val > 0:
                     break
                 
                 # val fails, ignore it
                 if abs(val) < abs(ret[-1]):
                     append_flag = False
                     break
 
                 # [-5, 5]
                 if val + ret[-1] == 0:
                     ret.pop()
                     append_flag = False
                     break
                 
                 ret.pop()
                 
             if append_flag:
                 ret.append(val)
                 
         return ret
     


class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         stack = []
         for a in asteroids:
             if a >= 0 or a < 0 and (not stack or stack[-1] < 0):
                 stack.append(a)
             else:
                 while a < 0 and stack and stack[-1] > 0:
                     last = stack.pop() # last > 0
                     a = a if -a > last else last if -a < last else 0
                 if a != 0:
                     stack.append(a)
         
         return stack

class Solution:
     def asteroidCollision(self, asteroids):
         """
         :type asteroids: List[int]
         :rtype: List[int]
         """
         stack = []
         for a in asteroids:
             if a >= 0 or a < 0 and (not stack or stack[-1] < 0):
                 stack.append(a)
             else:
                 while a < 0 and stack and stack[-1] > 0:
                     last = stack.pop() # last > 0
                     a = a if -a > last else last if -a < last else 0
                 if a != 0:
                     stack.append(a)
         
         return stack