Problem Statement

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

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.

Examples

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(); // returns -3
minStack.pop();
minStack.top();  // returns 0
minStack.getMin(); // returns -2

Example 2:

Input:["MinStack", "push", "push", "getMin", "push", "pop", "getMin", "top"]
[ [ ], [5], [1], [ ], [3], [ ], [ ], [ ] ]

Output: [null, null, null, 1, null, null, 1, 1]

Explanation:
MinStack minStack = new MinStack();
minStack.push(5);
minStack.push(1);
minStack.getMin(); // returns 1
minStack.push(3);
minStack.pop();
minStack.getMin(); // returns 1
minStack.top();  // returns 1

Different Approaches

1️⃣ Brute Force Approach

Intuition:

In a usual stack data structure, there is no method to get the minimum element present in the stack in constant time. This can be overcome, if all the numbers are stored in pairs with their current minimum element. This way, the stack will not only able to perform the previous methods in constant time, but also perform the getMin() method in constant time.

Note: The stack will store the following pair: {element, current minimum}

Approach:

1. A stack of pairs is used. Each pair contains the element itself and the minimum element at the time the element was pushed onto the stack. The MinStack class is initialized with an empty stack.
2. Push Operation: When a new element is pushed, it is compared with the current minimum. The new element and the updated minimum are stored as a pair and pushed onto the stack.
3. Pop Operation: The top element (which is a pair) is removed from the stack.
4. Top Operation: The top element of the stack is accessed to get the actual value (first component) stored.
5. GetMin Operation: The second value of the pair at the top of the stack, which represents the minimum element at that point, is accessed.

Code:

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

// Class to implement Minimum Stack
class MinStack {
private:
    // Initialize a stack
    stack <pair<int,int>> st;
    
public:
    
    // Empty Constructor
    MinStack() {
    }
    
    // Method to push a value in stack
    void push(int value) {
        
        // If stack is empty
        if(st.empty()) {
            
            // Push current value as minimum
            st.push( {value, value} );
            return;
        }
        
        // Update the current minimum 
        int mini = min(getMin(), value);
        
        // Add the pair to the stack
        st.push({value, mini});
    }
    
    // Method to pop a value from stack
    void pop() {
        // Using in-built pop method
        st.pop(); 
    }
    
    // Method to get the top of stack
    int top() {
        // Return the top value
        return st.top().first;
    }
    
    // Method to get the minimum in stack
    int getMin() {
        // Return the minimum
        return st.top().second;
    }
};

int main() {
    MinStack s;
    
    // Function calls
    s.push(-2);
    s.push(0);
    s.push(-3);
    cout << s.getMin() << " ";
    s.pop();
    cout << s.top() << " ";
    s.pop();
    cout << s.getMin();
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(1) All the operations take constant time.
• Space Complexity:O(2*N) (where N is the total number of calls made for push operation)
  • All the numbers are stored in pairs leading to a stack space of O(2*N).

2️⃣ Optimal Approach

Intuition:

To efficiently keep track of the minimum element in the stack at all times while maintaining constant time complexity for each operation, a clever approach is needed. This can be achieved by modifying the values stored in the stack when a new minimum is encountered. Instead of storing pairs or auxiliary stacks, we store a specially calculated value that allows us to track the minimum.

Approach:

1. Use a stack to store elements. Maintain a variable to keep track of the current minimum value.
2. Push Operation:
   1. If the stack is empty, push the value and set it as the current minimum.
   2. If the value is greater than or equal to the current minimum, push the value.
   3. If the value is less than the current minimum, push a modified value calculated using the new value and update the current minimum.
3. Pop Operation:
   1. If the stack is empty, do nothing. Otherwise, Retrieve and pop the top value.
   2. If the popped value indicates it was used to store a new minimum, update the current minimum using the retrieved value.
4. Top Operation:
   1. If the stack is empty, return -1 indicating the stack is empty.
   2. Retrieve the top value. If the top value is greater than or equal to the current minimum, return it.
   3. If the top value indicates it was used to store a new minimum, return the current minimum.
5. GetMin Operation: Simply return the current minimum.

Code:

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

// Class to implement Minimum Stack
class MinStack {
private:
    // Initialize a stack
    stack <int> st;
    // To store the minimum value 
    int mini;
    
public:
    
    // Empty Constructor
    MinStack() {
    }
    
    // Method to push a value in stack
    void push(int value) {
        
        // If stack is empty
        if(st.empty()) {
            //Update the minimum value
            mini = value;
            
            // Push current value as minimum
            st.push( value );
            return;
        }
        
        // If the value is greater than the minimum
        if(value > mini) {
            st.push(value);
        }
        else {
            // Add the modified value to stack
            st.push(2 * value - mini);
            // Update the minimum
            mini = value;
        }
    }
    
    // Method to pop a value from stack
    void pop() {
        // Base case
        if(st.empty()) return;
        
        // Get the top
        int x = st.top();
        st.pop(); // Pop operation
        
        // If the modified value was added to stack
        if(x < mini) {
            // Update the minimum
            mini = 2 * mini - x;
        }
    }
    
    // Method to get the top of stack
    int top() {
        // Base case
        if(st.empty()) return -1;
        
        // Get the top
        int x = st.top();
        
        // Returnn top if minimum is less than the top
        if(mini < x) return x;
        
        //Otherwise return mini
        return mini;
    }
    
    // Method to get the minimum in stack
    int getMin() {
        // Return the minimum
        return mini;
    }
};

int main() {
    MinStack s;
    
    // Function calls
    s.push(-2);
    s.push(0);
    s.push(-3);
    cout << s.getMin() << " ";
    s.pop();
    cout << s.top() << " ";
    s.pop();
    cout << s.getMin();
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(1) All the operations take constant time.
• Space Complexity:O(N) (where N is the total number of calls made for push operation)
  • As only one value per element is stored in the stack.