Problem statement
Contest source
Author , Tester , Editorialist : Jashwanth
DIFFICULTY:
medium
PREREQUISITES:
stack,STL
PROBLEM:
we are being asked to find the final stack after all possible collisions and explosions
EXPLANATION:
we use the concept of stack to solve this problem
- Create a stack object to store missiles.
- Loop missiles from 0 to N
- a) collision loop: while stack is not empty and the missile is negative and last value is positive
- if peek’s size is less than current missile then pop last element and continue the loop
- if peek’s size is equal to current missile then pop the last element and break collision loop
- push the missile to stack
-
Add all the remaining elements from list to integer array and return.
which is the required answer
SOLUTION :
class Solution(object):
def missileCollision(self, missiles):
stack = []
for num in missiles:
element = num
if element > 0:
stack.append(element)
else:
# left direction
while len(stack) != 0 and stack[-1] > 0:
top_element = stack[-1]
# eliminate current node
if top_element > -element:
element = None
break
elif top_element == -element:
# eliminiate both
stack.pop()
element = None
break
else:
# eliminate stack top. Then recursive check
stack.pop()
if element:
stack.append(element)
return stack
N=int(input())
l= input()
l=l.split()
for i in range(0,N):
l[i]=int(l[i])
s = Solution()
for k in s.missileCollision(l):
print(k,end=" ")