Min Stack

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

1.push(x) -- Push element x onto stack.

2.pop() -- Removes the element on top of the stack.

3.top() -- Get the top element.

4.getMin() -- Retrieve the minimum element in the stack.

Example:

Input:  arr={-2,0,-3}, getMin
Output: -3

Approach

C++

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

vector<int> v;
int min1 = INT_MAX;

void push(int x)
{
    if (x < min1)
        min1 = x;
    v.push_back(x);
}

int top()
{
    return v[v.size() - 1];
}

void pop()
{
    int x = top();
    v.pop_back();
    if (x == min1)
    {
        min1 = INT_MAX;
        for (int i : v)
            if (i < min1)
                min1 = i;
    }
}

int getMin()
{
    return min1;
}

int main()
{
    push(-2);
    push(0);
    push(-3);
    cout << getMin();

    return 0;
}