# Efficient algorithm for a modified stack to pop the smallest element

I was practicing the following problem :

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
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.

-

You can simply push elements to the stack only if they are smaller than the element on the top of the stack.If they are bigger you will count them in different counter in order to know how much elements were pushed and keep those counters in another stack. When you have to pop you will pop only the top element.

Here is sample pseudo code (some check for empty stacks and initial values are omitted):

    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.

-
Even the sample test cases is not passing with the approach u mentioned.Sorry if , i pick the logic ,incorrectly. Can you plz explain ur approach for the sample test cases –  Chopra Jack Dec 3 '12 at 14:08
I have added how it should look like for your example.Do not copy the code as it is -it just illustrates the idea. Keep in mind that you have error: "[9 2 3 1 2 10 5* ]" thi minimum here is 1 ,not 2 as you wrote. –  Anton Dec 3 '12 at 14:30
Thanks It worked. The above solution is quite faster . Thank you Anton :) :) –  Chopra Jack Dec 3 '12 at 21:39