C++     Design     Medium     Stack    

Problem Statement:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

 

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

 

Constraints:

  • -231 <= val <= 231 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 104 calls will be made to push, pop, top, and getMin.

Solution:

We use pre-built stack class but with our own class object instead of int which will have information on minimum value at any point on stack.

 
class Item
{
    public:
    int val;
    int minVal;
    Item(int v, int mv): val(v), minVal(mv){}
};

class MinStack {
    stack<Item> stk;
public:
    MinStack() 
    {}
    
    void push(int val) 
    {
        int m = (stk.empty()) ? val : min(stk.top().minVal, val);
        stk.push(Item(val, m));
    }
    
    void pop() 
    {
        stk.pop();
    }
    
    int top() 
    {
        return stk.top().val;
    }
    
    int getMin() 
    {
        return stk.top().minVal;
    }
};