Efficient /Fast Algorithm for the Modified Stack Implementation
I was practicing the following problem :
There are total N operations . At each operation , you can either add element to the top or removes few elements as described below. The input (integer) other than -1 indicates that we have to add the elements in last in first out fashion(LIFO). If the input is -1 at a time, then we have to remove (pop) all the elements that lie above the Minimum element (at that instant)in the stack .We should also pop that minimum element.
For each "-1" in the inputs ,print (m,p). m->the minimum elements in the stack and p-> 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 . 143
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 the simple stack for the above problem. But the constraint is high 1<=N<=10^6 There are many -1 in the input , so the simple stack will work very slow. The Time limit for the problem is just 1 second . Thank You! 143