There are a total of $N$ operations. At each operation, you can either add an element to the top or remove several elements as described below. Inputs are integers. An input other than $-1$ indicates that we have to add the elements in last in first out fashion (LIFO). If the input is $-1$, then we have to remove (pop) all the elements that lie above the current minimum element of the stack, and then pop that minimum element. For each $-1$ in the inputs, print $(m,p)$ where $m$ is the minimum element on the stack and $p$ counts how many total elements we popped from the stack.
Example :
N=14 (Total 4 operations) 9 6 8 -1 2 0 6 -1 3 1 2 10 5 -1 In above example : First three operation is inserting operation , that is we need to insert them in LIFO Fashion. So the stack after third operation is : [9 6 8*] PLEASE NOTE * represent the element at the top of the stack. Fourth Operation is -1 , that is we have to remove all elements (including the minimum ) , that lie above the minimun elements. The Minimum Element is 6 ,so we remove 8 and 6 and Hence the stack now is : [9*] So answer for fourth operation is (6,2) 6 - the minimum element in the stack and 2 ,as we removed total 2 elements from the stack. Operation 5 th ,6 th and 7th are Inserting operations. After 4 th operation , the stack was [9*] After 7th operation , the stack looks like [9 2 0 6*] 8th operation is -1 . Minimum element is 0 ,so we should remove 0,6 from the stack Hence Answer is (0,2) As the minimum element is "0" and we removed total "2" elements from the stack. The stack at the end of eighth operation is: [9 2] Operation 9 ,10 ,11 12,13 are inserting operations So Stack after 13th operation is: [9 2 3 1 2 10 5* ] operation 14 is -1. The minimum element in the stack is 2. However 2 lies at two different positions in the stack . But we should remove that 2 , which is nearest to the top of the stack (In order word ,if the minimum lies at more than two positions in the stack ,then the one which is closer to the top of the stack is considered). So remove 2 at Index 5 (as it is closer to the top of stack) and element that lies above it in stack. So after removing 2(the minimum element ) and 10,5 (the elements above the min element) The stack looks like: [9 2 3 1*] Answer is (2,3) //As 2 is the min element and we popped "3" elements PLEASE NOTE * represent the element at the top of the stack.
My approach
I am using a simple stack for the above problem. But the constraint is high: $1 le N le 10^6$. There are many $-1$’s in the input, so a simple stack will work very slowly. The time limit for the problem is just 1 second.
Asked By : Chopra Jack
Answered By : Anton
input: element // stack.peak() - gets top element without popping it if (element == -1) top = stack.pop() print(top, (counter_stack.pop() +1)) if (element > stack.peak()) count = counter_stack.pop() counter_stack.push(count+1) else stack.push(element) counter_stack.push(0)
Here is what should this look for your example:
9 stack: [9*] counter_stack: [0] 6 stack: [9 6*] counter_stack: [0 0] 8 stack: [9 6*] counter_stack: [0 1*] -1 stack: [9 6*] counter_stack: [0] print : 6(the popped value), 2 (counter_stack popped +1) 2 stack: [9*] counter_stack: [0 0] 0 stack: [9 2 0*] counter_stack: [0 0 0] 6 stack: [9 2 0*] counter_stack: [0 0 1] -1 stack: [9 2*] counter_stack: [0 0] print : 0(the popped value), 2 (counter_stack popped +1) 3 stack: [9 2*] counter_stack: [0 0 1*] 1 stack: [9 2 1*] counter_stack: [0 1 0*] 2 stack: [9 2 1*] counter_stack: [0 1 1*] 10 stack: [9 2 1*] counter_stack: [0 1 2*] 5 stack: [9 2 1*] counter_stack: [0 1 3*] -1 stack: [9 2*] counter_stack: [0 1] print : 1(the popped value), 4 (counter_stack popped +1) and so on.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7124
