155_min_stack.cpp

/*
LeetCode 155 - Min Stack
Difficulty: Medium

Problem:
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.

Example 1:
    Input:  ["MinStack","push","push","push","getMin","pop","top","getMin"]
            [[],[-2],[0],[-3],[],[],[],[]]
    Output: [null,null,null,null,-3,null,0,-2]

Constraints:
    -2^31 <= val <= 2^31 - 1
    Methods pop, top and getMin operations will always be called on non-empty stacks.
    At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Time Complexity: O(1) for all operations
Space Complexity: O(n)
*/

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

class MinStack {
private:
    stack<int> st;
    stack<int> min_st; // Tracks the current minimum at each level

public:
    MinStack() {
    }

    void push(int val) {
        st.push(val);
        int min_val = val;
        if (!min_st.empty()) {
            min_val = min(val, min_st.top());
        }
        min_st.push(min_val);
    }

    void pop() {
        st.pop();
        min_st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return min_st.top();
    }
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    cout << minStack.getMin() << endl; // -3
    minStack.pop();
    cout << minStack.top() << endl;    // 0
    cout << minStack.getMin() << endl; // -2

    return 0;
}