/*
   Leet Code 155. Min Stack

   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:

   -2^31 <= val <= 2^31 - 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.


   "I used two stacks — one for values, one that keeps non-increasing minima."
   "I push to the min stack only when val <= current min to correctly handle duplicate minimums."
   "In pop(), I compare before popping the main stack, but because the problem guarantees non-empty stacks, it's safe."
   "If the problem didn't have that guarantee, I would capture the top value first or add empty checks."
   "Space is O(n) in worst case (strictly decreasing sequence), but
   often much better in practice."
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

// Here is a clean, interview-ready implementation of MinStack using
// only one stack — a common follow-up question in Bloomberg-style
// interviews after the two-stack solution. The idea is to store both
// the value and the current minimum in each stack entry, usually as a
// pair (value, current_min). This keeps extra space O(n) but uses
// only one actual stack data structure.
*/

class MinStack {
public:
    // Normal stack handles push, pop, top in O(1)

    stack<int> m_stack;
    stack<int> m_minStack;
    
    MinStack() {
        
    }

    // Only push to min_stack if val <= current min
    void push(int val) {
        m_stack.push(val);
        if (m_minStack.empty() || val <= m_minStack.top())
            m_minStack.push(val);
    }

    // Only pop from min_stack if we removed the current minimum
    void pop() {
        // better to capture stack top
        int val = m_stack.top();
        m_stack.pop();
        
        if (val == m_minStack.top())
            m_minStack.pop();
    }
    
    int top() {
        return m_stack.top();
    }
    
    int getMin() {
        return m_minStack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */


int main(void)
{
    // Input
    // ["MinStack","push","push","push","getMin","pop","top","getMin"]
    // [[],[-2],[0],[-3],[],[],[],[]]

    // Output
    // [null,null,null,null,-3,null,0,-2]
    
    MinStack* obj = new MinStack();
    vector<int> a{-2,0,-3};
    for (const auto i: a)
        obj->push(i);
    
    int min;

    min = obj->getMin();
    EXPECT_EQ(min, -3);

    obj->pop();
    EXPECT_EQ(obj->top(), 0);

    min = obj->getMin();
    EXPECT_EQ(min, -2);

    return 0;
}