Min Stack

In min stack problem we have to design a stack to implement the following functions efficiently,
push(x) –> Push an element x to the stack
pop() –> Removes the item on top of stack
top() –> Return the element at top of stack
getMin() –> Return the minimum element present in the stack

Example

Input:
Push -2
Push 0
Get Min
Push -3
Pop
Top
Get Min
Output:
-2
0
-2

Algorithm for Min Stack

push, pop, and top method are similar to a normal stack, but to get the minimum element present in the stack we use one more stack that stores the minimum value till every element.

Let the first stack be st and second stack be minSt, then

push(x)

1. Push x to the stack st.
2. If minSt is empty or if the top of minSt is greater than x push x to minSt.
3. Else push the top of minSt to minSt again.

Time Complexity=O(1) 
Space Complexity =O(1)

pop()

Pop an element from stack st and also from stack minSt.

Time Complexity=O(1) 
Space Complexity=O(1)

top()

Return the top of stack st.

Time Complexity=O(1) 
Space Complexity=O(1)

getMin()

Return the top of stack minSt.

Time Complexity=O(1) 
Space Complexity=O(1)

Overall Space Complexity = O(n) 
where n is the maximum number of elements pushed into the stack at a time.

Explanation for Min Stack

Consider the example above,
Initialize two stack st and minSt.
st = null and minSt = null

1. Push (-2)
   st= (-2) and minSt= (-2)
2. Push 0
   st= 0 -> (-2) and minSt= (-2) -> (-2)
3. getMin
   Top of minSt = (-2), return (-2)
4. Push (-3)
   st = (-3) -> 0 -> (-2) and minSt= (-3) -> (-2) -> (-2)
5. Pop
   st = 0 -> (-2) and minSt = (-2) -> (-2)
6. Top
   Top of stack st is 0, return 0.
7. getMin
   Top of stack minSt is (-2), return (-2).

See the image below for clarification.

JAVA Code for Min Stack

import java.util.Stack;

public class MinStack {
    private static Stack<Integer> st;
    private static Stack<Integer> minSt;

    private static void push(int x) {
        // Push x to stack st
        st.push(x);
        // If minSt is empty or if top of minSt is greater than x push x to minSt.
        if (minSt.isEmpty() || minSt.peek() > x) {
            minSt.push(x);
        } else {
            // Else push top of minSt to minSt again.
            minSt.push(minSt.peek());
        }
    }

    private static void pop() {
        // Pop element from st and minSt
        st.pop();
        minSt.pop();
    }
    
    private static int top() {
        // Return top of st
        return st.peek();
    }
    
    private static int getMin() {
        // Return top of minSt
        return minSt.peek();
    }

    public static void main(String[] args) {
        // Initialise st and minSt
        st = new Stack<>();
        minSt = new Stack<>();

        // Example
        push(-2);
        push(0);
        System.out.println(getMin());
        push(-3);
        pop();
        System.out.println(top());
        System.out.println(getMin());
    }
}

-2
0
-2

C++ Code for Min Stack

#include<bits/stdc++.h> 
using namespace std;

stack<int> st;
stack<int> minSt;

void push(int x) {
    // Push x to stack st
    st.push(x);
    // If minSt is empty or if top of minSt is greater than x push x to minSt.
    if (minSt.empty() || minSt.top() > x) {
        minSt.push(x);
    } else {
        // Else push top of minSt to minSt again.
        minSt.push(minSt.top());
    }
}

void pop() {
    // Pop element from st and minSt
    st.pop();
    minSt.pop();
}

int top() {
    // Return top of st
    return st.top();
}

int getMin() {
    // Return top of minSt
    return minSt.top();
}

int main() {
    // Example
    push(-2);
    push(0);
    cout<<getMin()<<endl;
    push(-3);
    pop();
    cout<<top()<<endl;
    cout<<getMin()<<endl;
    
    return 0;
}

-2
0
-2

References