Efficient algorithm for a modified stack to pop the smallest element

Question

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

Answer 1

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.