We are given an integer array asteroids of size N 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 of same size, both will explode. Two asteroids moving in the same direction will never meet.
 
Example 1:
Input:
N = 3
asteroids[ ] = {3, 5, -3}
Output: {3, 5}
Explanation: The asteroid 5 and -3 collide resulting in 5. The 5 and 3 never collide.
Example 2:
Input:
N = 2
asteroids[ ] = {10, -10}
Output: { }
Explanation: The asteroid -10 and 10 collide exploding each other.
Your Task:
You don't need to read input or print anything. Your task is to complete the function asteroidCollision() which takes the array of integers asteroids and N as parameters and returns the state of asteroids after all collisions.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
-1000 ≤ asteroids_{i  }≤ 1000
asteroids[i]!=0

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def asteroidCollision(self, N, asteroids):

        # Code here

Solutions:
class Solution:

	def asteroidCollision(self, N, asteroids):
		st = []
		for i in range(len(asteroids)):
			while st and asteroids[i] < 0 and (st[-1] > 0):
				if abs(asteroids[i]) > abs(st[-1]):
					st.pop()
					continue
				elif abs(asteroids[i]) == abs(st[-1]):
					st.pop()
				break
			else:
				st.append(asteroids[i])
		return st


class Solution:

	def asteroidCollision(self, N, arr):
		stack = []
		for e in asteroids:
			if len(stack) == 0 or e > 0:
				stack.append(e)
				continue
			while len(stack) > 0 and stack[-1] > 0:
				if abs(e) > stack[-1]:
					stack.pop()
				else:
					if abs(e) == stack[-1]:
						stack.pop()
					break
			else:
				stack.append(e)
		return stack


class Solution:

	def asteroidCollision(self, N, arr):
		stack = []
		for asteroid in asteroids:
			while stack and asteroid < 0 and (stack[-1] > 0):
				if stack[-1] < -asteroid:
					stack.pop()
					continue
				elif stack[-1] == -asteroid:
					stack.pop()
				break
			else:
				stack.append(asteroid)
		return stack


class Solution:

	def asteroidCollision(self, n, arr):
		ans = [arr[0]]
		leng = 1
		for i in range(1, n):
			if ans[leng - 1] > 0 and arr[i] < 0:
				flag = 0
				while leng > 0:
					if abs(arr[i]) > abs(ans[leng - 1]) and ans[leng - 1] > 0:
						flag = 1
						ans.pop()
						leng -= 1
					elif abs(arr[i]) == abs(ans[leng - 1]) and ans[leng - 1] > 0:
						ans.pop()
						flag = 0
						leng -= 1
						break
					else:
						if ans[leng - 1] > 0:
							flag = 0
						break
				if flag == 1:
					ans.append(arr[i])
					leng += 1
			elif ans[leng - 1] < 0 and arr[i] < 0 or (ans[leng - 1] > 0 and arr[i] > 0) or (ans[leng - 1] < 0 and arr[i] > 0):
				ans.append(arr[i])
				leng += 1
		return ans


class Solution:

	def asteroidCollision(self, N, asteroids):
		s = []
		i = 0
		while i < N:
			if len(s) == 0:
				s.append(asteroids[i])
				i += 1
			elif asteroids[i] > 0:
				s.append(asteroids[i])
				i += 1
			elif s[-1] > 0:
				if s[-1] > abs(asteroids[i]):
					i += 1
				elif s[-1] == abs(asteroids[i]):
					s.pop()
					i += 1
				else:
					s.pop()
					i = i
			else:
				s.append(asteroids[i])
				i += 1
		return s


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for i in asteroids:
			while len(stack) > 0 and stack[-1] > 0 and (i < 0):
				if stack[-1] < abs(i):
					stack.pop()
				elif stack[-1] > abs(i):
					i = 0
				elif stack[-1] == abs(i):
					stack.pop()
					i = 0
			if i > 0 or i < 0:
				stack.append(i)
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for a in asteroids:
			while stack and a < 0 and (stack[-1] > 0):
				dif = a + stack[-1]
				if dif < 0:
					stack.pop()
				elif dif > 0:
					break
				else:
					stack.pop()
					break
			else:
				stack.append(a)
		return stack


class Solution:

	def asteroidCollision(self, N, l):
		s = []
		if len(l) < 2:
			return l
		else:
			for i in l:
				x = 0
				y = 0
				while s and (i < 0 and s[-1] > 0):
					if abs(i) > abs(s[-1]):
						s.pop()
					elif abs(i) == abs(s[-1]):
						s.pop()
						x = x + 1
						break
					else:
						y = y + 1
						break
				if x > 0 or y > 0:
					pass
				else:
					s.append(i)
			return s


class Solution:

	def asteroidCollision(self, N, asteroids):
		ans = []
		i = 0
		while i < len(asteroids) and asteroids[i] < 0:
			ans.append(asteroids[i])
			i += 1
		while i < len(asteroids):
			if asteroids[i] < 0:
				while ans and ans[-1] > 0:
					if ans[-1] < -asteroids[i]:
						ans.pop()
					elif ans[-1] == -asteroids[i]:
						ans.pop()
						break
					else:
						break
				else:
					ans.append(asteroids[i])
			else:
				ans.append(asteroids[i])
			i += 1
		return ans


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for i in range(0, N):
			asteroid = asteroids[i]
			is_equal_collision = False
			while stack:
				collision = not self.check_same_sign(asteroid, stack[-1])
				if not collision:
					stack.append(asteroid)
					break
				elif asteroid > 0:
					stack.append(asteroid)
					break
				elif abs(asteroid) > abs(stack[-1]):
					stack.pop()
				elif abs(asteroid) == abs(stack[-1]):
					is_equal_collision = True
					stack.pop()
					break
				else:
					break
			if not is_equal_collision and len(stack) == 0:
				stack.append(asteroid)
		return stack

	def check_same_sign(self, a, b):
		if a > 0 and b > 0 or (a < 0 and b < 0):
			return True
		return False


class Solution:

	def asteroidCollision(self, N, asteroids):
		st = []
		for ele in asteroids:
			flag = 1
			while st and (st[-1] > 0 and ele < 0):
				if abs(ele) > abs(st[-1]):
					st.pop()
				elif abs(ele) == abs(st[-1]):
					flag = 0
					st.pop()
					break
				else:
					flag = 0
					break
			if flag == 1:
				st.append(ele)
		return st


class Solution:

	def asteroidCollision(self, n, arr):
		st = []
		for ele in arr:
			flag = 1
			while st and (st[-1] > 0 and ele < 0):
				if abs(ele) > abs(st[-1]):
					st.pop()
				elif abs(ele) == abs(st[-1]):
					flag = 0
					st.pop()
					break
				else:
					flag = 0
					break
			if flag == 1:
				st.append(ele)
		return st


class Solution:

	def sign(self, a):
		if a >= 0:
			return 1
		return 0

	def asteroidCollision(self, N, asteroids):
		lst = []
		for i in range(len(asteroids)):
			if len(lst) == 0:
				lst.append(asteroids[i])
			else:
				flag = 0
				while len(lst) and self.sign(lst[-1]) == 1 and (self.sign(asteroids[i]) == 0):
					if abs(lst[-1]) > abs(asteroids[i]):
						flag = 1
						break
					elif abs(lst[-1]) == abs(asteroids[i]):
						lst.pop()
						flag = 1
						break
					else:
						lst.pop()
				if flag == 0:
					lst.append(asteroids[i])
		return lst


class Solution:

	def asteroidCollision(self, N, arr):
		stack = []
		for num in arr:
			if num < 0:
				toadd = not stack or stack[-1] < 0
				while stack and stack[-1] > 0:
					toadd = False
					if stack[-1] == abs(num):
						stack.pop()
						break
					elif stack[-1] > abs(num):
						break
					else:
						toadd = True
						stack.pop()
				if toadd:
					stack.append(num)
			else:
				stack.append(num)
		return stack


class Solution:

	def asteroidCollision(self, N, a):
		stack = []
		for i in range(N):
			if len(stack) > 0 and (stack[-1] > 0 and a[i] < 0):
				if abs(stack[-1]) < abs(a[i]):
					stack.pop()
					flag = True
					while len(stack) > 0 and (stack[-1] > 0 and a[i] < 0):
						if abs(stack[-1]) < abs(a[i]):
							stack.pop()
						elif abs(stack[-1]) == abs(a[i]):
							stack.pop()
							flag = False
							break
						else:
							flag = False
							break
					if flag:
						stack.append(a[i])
					if len(stack) == 0:
						stack.append(a[i])
				elif abs(stack[-1]) == abs(a[i]):
					stack.pop()
			else:
				stack.append(a[i])
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		st = []
		for val in asteroids:
			if val > 0:
				st.append(val)
			else:
				while len(st) > 0 and st[-1] > 0 and (st[-1] < -1 * val):
					st.pop()
				if len(st) > 0 and st[-1] == -1 * val:
					st.pop()
				elif len(st) > 0 and st[-1] > -1 * val:
					pass
				else:
					st.append(val)
		return st


class Solution:

	def asteroidCollision(self, N, asteroids):
		flag = False
		while flag == False:
			for i in range(1, len(asteroids)):
				if asteroids[i - 1] > 0 and asteroids[i] < 0:
					if asteroids[i - 1] > -asteroids[i]:
						asteroids.pop(i)
					elif asteroids[i - 1] < -asteroids[i]:
						asteroids.pop(i - 1)
					else:
						asteroids.pop(i - 1)
						asteroids.pop(i - 1)
					flag = True
					break
			if flag == True:
				flag = False
			else:
				break
		return asteroids


class Solution:

	def asteroidCollision(self, N, asteroids):
		(i, j) = (0, 1)
		while i < len(asteroids) and j < len(asteroids):
			if asteroids[i] > 0 and asteroids[j] < 0 and (asteroids[i] > -1 * asteroids[j]):
				asteroids.pop(j)
			elif asteroids[i] > 0 and asteroids[j] < 0 and (asteroids[i] < -1 * asteroids[j]):
				asteroids.pop(i)
				if i > 0:
					i -= 1
					j -= 1
			elif asteroids[i] > 0 and asteroids[j] < 0 and (asteroids[i] == -1 * asteroids[j] or -1 * asteroids[i] == asteroids[j]):
				asteroids.pop(i)
				asteroids.pop(i)
				if i > 0:
					i -= 1
					j -= 1
			else:
				i += 1
				j += 1
		return asteroids


class Solution:

	def asteroidCollision(self, N, asteroids):
		st = []
		for i in asteroids:
			if i > 0:
				st.append(i)
			elif not st:
				st.append(i)
			elif st[-1] < 0:
				st.append(i)
			else:
				while st and st[-1] > 0 and (st[-1] < abs(i)):
					st.pop()
				if not st:
					st.append(i)
				elif st[-1] == abs(i):
					st.pop()
				elif st[-1] < 0:
					st.append(i)
		return st


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for a in asteroids:
			if not stack:
				stack.append(a)
			elif stack and a < 0:
				while stack and stack[-1] >= 0 and (abs(stack[-1]) < abs(a)):
					stack.pop()
				if stack:
					if stack[-1] < 0:
						stack.append(a)
					elif abs(stack[-1]) == abs(a):
						stack.pop()
					elif abs(stack[-1]) > abs(a):
						pass
				else:
					stack.append(a)
			else:
				stack.append(a)
		return stack


class Solution:

	def asteroidCollision(self, N, arr):
		st = []
		st.append(arr[0])
		for i in range(1, N):
			flag = True
			while st and st[-1] > 0 and (arr[i] < 0):
				if abs(arr[i]) > abs(st[-1]):
					st.pop()
				elif abs(arr[i]) == abs(st[-1]):
					flag = False
					st.pop()
					break
				else:
					break
			if st and flag:
				if st[-1] // abs(st[-1]) == arr[i] // abs(arr[i]) or (st[-1] <= 0 and arr[i] >= 0):
					st.append(arr[i])
			elif flag:
				st.append(arr[i])
		return st


class Solution:

	def asteroidCollision(self, N, asteroids):
		ans = []
		for i in asteroids:
			v = True
			if not ans:
				ans.append(i)
			elif i >= 0:
				ans.append(i)
			else:
				while ans and ans[-1] >= 0:
					if ans[-1] < abs(i):
						ans.pop()
					elif ans[-1] == abs(i):
						v = False
						ans.pop()
						break
					else:
						v = False
						break
				if v == True:
					ans.append(i)
		return ans


class Solution:

	def asteroidCollision(self, N, asteroids):
		for i in range(1, N):
			(low, high) = (i - 1, i + 1)
			while low >= 0 and asteroids[i] != float('inf') and (asteroids[i] < 0):
				if asteroids[low] == float('inf'):
					pass
				elif asteroids[low] > 0:
					if abs(asteroids[i]) > abs(asteroids[low]):
						asteroids[low] = float('inf')
					elif abs(asteroids[i]) < abs(asteroids[low]):
						asteroids[i] = float('inf')
					else:
						asteroids[low] = float('inf')
						asteroids[i] = float('inf')
				else:
					break
				low -= 1
			while high < N and asteroids[i] != float('inf') and (asteroids[i] > 0):
				if asteroids[high] == float('inf'):
					pass
				elif asteroids[high] < 0:
					if asteroids[i] > abs(asteroids[high]):
						asteroids[high] = float('inf')
					elif asteroids[i] < abs(asteroids[high]):
						asteroids[i] = float('inf')
					elif asteroids[i] == abs(asteroids[high]):
						asteroids[high] = float('inf')
						asteroids[i] = float('inf')
				else:
					break
				high += 1
		return [i for i in asteroids if i != float('inf')]


class Solution:

	def asteroidCollision(self, N, asteroids):
		s = []
		ans = []
		for i in range(N):
			if asteroids[i] >= 0:
				s.append(asteroids[i])
			else:
				while s and s[-1] > 0 and (abs(s[-1]) < abs(asteroids[i])):
					s.pop()
				if s:
					if s[-1] < 0 and asteroids[i] < 0:
						s.append(asteroids[i])
					elif s[-1] == abs(asteroids[i]):
						s.pop()
				else:
					s.append(asteroids[i])
		while s:
			ans.append(s.pop())
		ans.reverse()
		return ans


class Solution:

	def asteroidCollision(self, N, arr):
		stack = []
		for i in arr:
			while stack and i < 0 < stack[-1]:
				if abs(i) > stack[-1]:
					stack.pop()
					continue
				elif abs(i) == stack[-1]:
					stack.pop()
				break
			else:
				stack.append(i)
		return stack


class Solution:

	def asteroidCollision(self, N, ast):
		stack = []
		for i in ast:
			flag = 1
			while stack and (stack[-1] > 0 and i < 0):
				if abs(i) > stack[-1]:
					stack.pop()
				elif abs(i) == stack[-1]:
					flag = 0
					stack.pop()
					break
				else:
					flag = 0
					break
			if flag == 1:
				stack.append(i)
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for ele in asteroids:
			push = True
			while stack and (stack[-1] > 0 and ele < 0):
				if abs(ele) > abs(stack[-1]):
					stack.pop()
				elif abs(ele) == abs(stack[-1]):
					push = False
					stack.pop()
					break
				else:
					push = False
					break
			if push:
				stack.append(ele)
		return stack


class Solution:

	def asteroidCollision(self, n, a):
		pos = []
		neg = []
		ans = []
		for i in range(n):
			if a[i] > 0:
				pos.append(a[i])
				ans.append(a[i])
			else:
				if len(neg) == 0 and len(pos) == 0:
					ans.append(a[i])
				elif len(pos) == 0:
					ans.append(a[i])
				neg.append(a[i])
				x = a[i]
				while len(pos) > 0 and len(neg) > 0:
					if pos[-1] > -neg[-1]:
						if neg[-1] == x:
							neg.pop()
							break
					elif pos[-1] < -neg[-1]:
						pos.pop()
						ans.pop()
						if len(pos) == 0:
							ans.append(x)
					elif pos[-1] == -neg[-1]:
						pos.pop()
						ans.pop()
						if neg[-1] == x:
							neg.pop()
							break
		return ans


class Solution:

	def asteroidCollision(self, N, asteroids):
		ans = []
		for new in asteroids:
			while ans and new < 0 < ans[-1]:
				if ans[-1] < -new:
					ans.pop()
					continue
				elif ans[-1] == -new:
					ans.pop()
				break
			else:
				ans.append(new)
		return ans


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for i in asteroids:
			while stack and i < 0 and (stack[-1] > 0):
				diff = -i - stack[-1]
				if diff > 0:
					stack.pop()
				elif diff < 0:
					i = 0
				else:
					stack.pop()
					i = 0
			if i:
				stack.append(i)
		return stack


class Solution:

	def asteroidCollision(self, N, arr):
		x = []
		for i in range(len(arr)):
			if arr[i] > 0:
				x.append(arr[i])
			else:
				while len(x) != 0 and x[-1] < abs(arr[i]) and (x[-1] > 0):
					x.pop()
				if len(x) == 0 or x[-1] < 0:
					x.append(arr[i])
				elif x[-1] == abs(arr[i]):
					x.pop()
		return x


class Solution:

	def asteroidCollision(self, N, asteroids):
		res = []
		for new in asteroids:
			if not res:
				res.append(new)
			elif res[-1] < 0:
				res.append(new)
			elif new > 0:
				res.append(new)
			else:
				while res and res[-1] > 0:
					if res[-1] + new == 0:
						res.pop()
						break
					elif res[-1] + new < 0:
						res.pop()
						if not res or res[-1] < 0:
							res.append(new)
							break
					else:
						break
		return res


class Solution:

	def asteroidCollision(self, N, A):
		B = []
		for i in range(0, N):
			if len(B) > 0:
				f = 0
				f2 = 0
				while B[-1] > 0 and A[i] < 0:
					f2 = 1
					if B[-1] > abs(A[i]):
						f = 0
						break
					elif B[-1] == abs(A[i]):
						B.pop()
						f = 0
						break
					else:
						B.pop()
						f = 1
					if len(B) == 0:
						break
				if f == 1 or f2 == 0:
					B.append(A[i])
			else:
				B.append(A[i])
		return B


from collections import deque

class Solution:

	def asteroidCollision(self, n, a):
		st = deque()
		for val in a:
			if val > 0:
				st.append(val)
			else:
				while st and st[-1] > 0 and (st[-1] < -val):
					st.pop()
				if st and st[-1] == -val:
					st.pop()
				elif not st or st[-1] < -val:
					st.append(val)
		return st


class Solution:

	def asteroidCollision(self, N, asteroids):
		res = []
		for asteroid in asteroids:
			while len(res) and asteroid < 0 and (res[-1] > 0):
				if res[-1] == -asteroid:
					res.pop()
					break
				elif res[-1] < -asteroid:
					res.pop()
					continue
				elif res[-1] > -asteroid:
					break
			else:
				res.append(asteroid)
		return res


class Solution:

	def asteroidCollision(self, n, arr):
		st = []
		for i in range(n):
			if not st or arr[i] > 0:
				st.append(arr[i])
			else:
				while True:
					top = st[-1]
					if top < 0:
						st.append(arr[i])
						break
					elif top == -arr[i]:
						st.pop()
						break
					elif top > -arr[i]:
						break
					elif top < -arr[i]:
						st.pop()
						if not st:
							st.append(arr[i])
							break
		return st


class Solution:

	def asteroidCollision(self, N, asteroids):
		s = []
		for e in asteroids:
			f = 1
			while s and s[-1] > 0 and (e < 0):
				if abs(s[-1]) < abs(e):
					s.pop()
				elif abs(s[-1]) == abs(e):
					f = 0
					s.pop()
					break
				else:
					f = 0
					break
			if f == 1:
				s.append(e)
		return s


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []

		def remove(stack, last):
			if not stack or stack[-1] < 0 or i > 0:
				stack.append(i)
			elif abs(i) < abs(stack[-1]):
				return
			elif abs(i) == abs(stack[-1]):
				stack.pop()
			else:
				stack.pop()
				remove(stack, last)
		for i in asteroids:
			remove(stack, i)
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for i in asteroids:
			if not stack or stack[-1] < 0 or i > 0:
				stack.append(i)
			elif abs(i) < abs(stack[-1]):
				continue
			elif abs(i) == abs(stack[-1]):
				stack.pop()
			else:
				while stack and stack[-1] > 0 and (abs(stack[-1]) < abs(i)):
					stack.pop()
				if stack and stack[-1] > 0:
					if abs(stack[-1]) > abs(i):
						continue
					elif abs(stack[-1]) == abs(i):
						stack.pop()
						continue
				stack.append(i)
		return stack


class Solution:

	def asteroidCollision(self, N, a):
		st = []
		for i in range(N):
			if not st or a[i] > 0:
				st.append(a[i])
			else:
				while st and st[-1] > 0 and (st[-1] < abs(a[i])):
					st.pop()
				if len(st) and st[-1] == abs(a[i]):
					st.pop()
				elif not st or st[-1] < 0:
					st.append(a[i])
		return st


class Solution:

	def sign(self, no):
		if no > 0:
			return '+'
		else:
			return '-'

	def asteroidCollision(self, n, arr):
		stack = [arr[0]]
		for i in range(1, n):
			cur_sign = self.sign(arr[i])
			if stack:
				t_sign = self.sign(stack[-1])
				top = stack[-1]
			else:
				t_sign = cur_sign = self.sign(arr[i])
			cur = arr[i]
			case = '-1'
			if cur_sign == '-' and t_sign == '+':
				while stack and cur_sign == '-' and (t_sign == '+'):
					if abs(top) > abs(cur):
						break
					elif abs(cur) == abs(top):
						stack.pop()
						break
					elif abs(top) < abs(cur):
						case = '2'
						stack.pop()
					if case == '2':
						if stack == [] or self.sign(stack[-1]) == cur_sign:
							stack.append(cur)
							case = '-1'
							break
					if stack:
						top = stack[-1]
						t_sign = self.sign(stack[-1])
			else:
				stack.append(cur)
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		ans = []
		for i in asteroids:
			if not ans or ans[-1] < 0 or i > 0:
				ans.append(i)
				continue
			while ans and ans[-1] > 0 and (ans[-1] < -i):
				ans.pop()
			if not ans or ans[-1] * i >= 0:
				ans.append(i)
				continue
			if ans[-1] == -i:
				ans.pop()
		return ans


class Solution:

	def asteroidCollision(self, N, asteroids):
		s = []
		for i in asteroids:
			flag = 1
			while s and s[-1] > 0 and (i < 0):
				if abs(i) > abs(s[-1]):
					s.pop()
				elif abs(i) == abs(s[-1]):
					s.pop()
					flag = 0
					break
				else:
					flag = 0
					break
			if flag == 1:
				s.append(i)
		return s


class Solution:

	def asteroidCollision(self, N, A):
		stack = []
		for i in A:
			if not stack or stack[-1] < 0 or i > 0:
				stack.append(i)
			else:
				while stack and stack[-1] > 0 and (stack[-1] < -i):
					stack.pop()
				if not stack or stack[-1] * i >= 0:
					stack.append(i)
				elif stack[-1] == -i:
					stack.pop()
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		for item in asteroids:
			if item > 0 or not stack or stack[-1] < 0:
				stack.append(item)
				continue
			while stack and stack[-1] > 0 and (stack[-1] + item < 0):
				stack.pop()
			if not stack or stack[-1] < 0:
				stack.append(item)
			if stack[-1] + item == 0:
				stack.pop()
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		ans = []
		for i in asteroids:
			if i > 0:
				ans.append(i)
			else:
				while True:
					if len(ans) > 0:
						if ans[-1] < 0:
							ans.append(i)
							break
						elif ans[-1] < abs(i):
							del ans[-1]
						elif ans[-1] == abs(i):
							del ans[-1]
							break
						else:
							break
					else:
						ans.append(i)
						break
		return ans


from collections import deque

class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = deque()
		res = []
		for asteroid in asteroids:
			if asteroid > 0:
				stack.append(asteroid)
			else:
				colideFlag = False
				while stack and stack[-1] < -asteroid:
					stack.pop()
					colideFlag = True
				if stack and stack[-1] == -asteroid:
					stack.pop()
				elif not stack:
					res.append(asteroid)
		res.extend(stack)
		return res


class Solution:

	def asteroidCollision(self, N, asteroids):
		lst = [0]
		i = 0
		while i != len(asteroids):
			if abs(asteroids[i]) > lst[-1] and lst[-1] > 0 > asteroids[i]:
				lst.pop()
			elif abs(asteroids[i]) < lst[-1] and lst[-1] > 0 > asteroids[i]:
				i += 1
			elif abs(asteroids[i]) == lst[-1] and lst[-1] > 0 > asteroids[i]:
				lst.pop()
				i += 1
			else:
				lst.append(asteroids[i])
				i += 1
		lst.remove(0)
		return lst


class Solution:

	def asteroidCollision(self, N, asteroids):
		asteroids_list = list()
		for i in asteroids:
			if i > 0 or len(asteroids_list) == 0:
				asteroids_list.append(i)
			else:
				while len(asteroids_list) != 0 and asteroids_list[-1] > 0 and (asteroids_list[-1] < abs(i)):
					asteroids_list.pop()
				if len(asteroids_list) != 0 and asteroids_list[-1] < 0:
					asteroids_list.append(i)
				elif len(asteroids_list) == 0 or asteroids_list[-1] < 0:
					asteroids_list.append(i)
				elif len(asteroids_list) != 0 and asteroids_list[-1] == abs(i):
					asteroids_list.pop()
		return asteroids_list


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		res = []

		def process(a, b):
			if abs(a) > abs(b):
				return a
			elif abs(a) == abs(b) and a * b < 0:
				return 0
			else:
				return b
		for x in asteroids:
			if not stack:
				stack.append(x)
				continue
			if stack[-1] < 0:
				stack.append(x)
			elif x < 0:
				new = x
				while stack and stack[-1] > 0 and (new < 0):
					new = process(stack.pop(), new)
					if new == 0:
						break
				if new != 0:
					stack.append(new)
			else:
				stack.append(x)
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		stk = []
		for i in range(len(asteroids)):
			if asteroids[i] < 0:
				self.handleLeft(asteroids[i], stk)
			else:
				stk.append(asteroids[i])
		toreturn = [stk.pop() for _ in range(len(stk))][::-1]
		return toreturn

	def handleLeft(self, asteroid, stk):
		if not stk or stk[-1] < 0:
			stk.append(asteroid)
		else:
			pop = stk.pop()
			if pop == -1 * asteroid:
				return
			else:
				toPush = pop if pop > abs(asteroid) else asteroid
				if toPush < 0:
					self.handleLeft(toPush, stk)
				else:
					stk.append(toPush)


class Solution:

	def asteroidCollision(self, N, asteroids):
		stack = []
		asteroids.reverse()
		while asteroids:
			if not stack:
				stack.append(asteroids.pop())
			elif stack[-1] < 0 or asteroids[-1] > 0:
				stack.append(asteroids.pop())
			elif stack[-1] + asteroids[-1] == 0:
				stack.pop()
				asteroids.pop()
			elif stack[-1] + asteroids[-1] > 0:
				asteroids.pop()
			elif stack[-1] + asteroids[-1] < 0:
				stack.pop()
		return stack


class Solution:

	def asteroidCollision(self, N, asteroids):
		ans = []
		stack = []
		for val in asteroids:
			if val < 0:
				left = val
				while len(stack) > 0:
					y = stack.pop()
					if y + val == 0:
						left = None
						break
					if y + val > 0:
						left = y
						stack.append(y)
						break
				if left == val:
					ans.append(val)
			if val > 0:
				stack.append(val)
		return ans + stack


class Solution:

	def asteroidCollision(self, N, arr):
		stack1 = [arr[0]]
		for i in range(1, N):
			if stack1 != []:
				break1 = 'no'
				while stack1 != []:
					if stack1[-1] > 0 and arr[i] < 0:
						if abs(stack1[-1]) == abs(arr[i]):
							stack1.pop()
							break1 = 'yes'
							break
						elif abs(stack1[-1]) < abs(arr[i]):
							stack1.pop()
						else:
							break1 = 'yes'
							break
					else:
						break
				if (stack1 == [] or (stack1[-1] >= 0 and arr[i] >= 0) or (stack1[-1] <= 0 and arr[i] <= 0) or (stack1[-1] <= 0 and arr[i] >= 0)) and break1 == 'no':
					stack1.append(arr[i])
			else:
				stack1.append(arr[i])
		return stack1