Implement push, pop, min in O(1) performance

 

Introduction

   This is a popular interview question found in a site. (ihas1337code). You need to implement push, pop, min all with just O(1) performance. You can use extra space and you can do any push & pops. Every time you should get the minimum in the stack using the min function.

Concept

  Do do this, you need 2 stacks. One which maintains all the minimums found until then and one which contains all the numbers.

For example, the main stack is.

3

2

10

1

7

5

9

The stack with all the min’s found will be

1

5

9

NaN

 

Now, when you pop from the main stack, make sure that you pop the min stack as well only when the element is equal to the popping element.

So, if we have pop-ed 3,2,10, we will still have 1 as min in the min stack. Remove 1 as well in the main stack, you must remove 1 in the min stack as well. Now, definitely 5 is the min.

  With this approach, you can implement pop, push, min all in O(1).

Code

class PerStack

{

    int arr1[100];

    int arr2[100];

    int top1;

    int top2;

public:

    PerStack() : top1(0), top2(0) {

        arr2[0] = INT_MAX;

    }

    void push(int val)

    {

        arr1[top1++] = val;

        if(val < arr2[top2] )

        {

            arr2[++top2] = val;

        }

    }

    int pop()

    {

        if(arr1[top1] == arr2[top2])

            arr2[top2--] = INT_MIN;

        return arr1[--top1];

    }

    int min() {

        return arr2[top2];

    }

};

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    PerStack n;

    for(int i=0; i<7;i++)

        n.push(A[i]);

    cout<<"minimum : "<<n.min();

}