1
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Dec 3, 2012 at 14:08
  • $\begingroup$ 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. $\endgroup$
    – Anton
    Dec 3, 2012 at 14:30
  • $\begingroup$ Thanks It worked. The above solution is quite faster . Thank you Anton :) :) $\endgroup$ Dec 3, 2012 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.