DAY 105 - 155. Min Stack

Hey Guys! Welcome back to another day. Today we will be moving onto stacks from our linked lists and we are back with a very good question.

Question: 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

Understanding the MinStack:

• push(val): This operation adds an element, val, to the stack. It also needs to keep track of the minimum element in the stack.

• pop(): This operation removes the top element from the stack.

• top(): This operation returns the top element of the stack without removing it.

• getMin(): This operation returns the minimum element currently present in the stack in constant time.

Approach:

To implement the MinStack, we can use two separate stacks: one to store the actual elements (st) and another to keep track of the indices of minimum elements (miniVals). Here's how our approach works:

• We maintain two vectors, st and miniVals, to represent the stack and store the indices of minimum elements, respectively.

• When pushing a new element onto the stack (push(val)), we compare it with the current minimum element. If it's smaller, we push the index of the new element onto miniVals. This way, we always have a reference to the index of the minimum element in the stack.

• When popping an element from the stack (pop()), we simply remove the top element from st. If the index of the minimum element (miniVals.back()) matches the index of the element being removed, we also remove it from miniVals.

• Retrieving the top element (top()) is straightforward; we return the last element of st.

• To get the minimum element (getMin()), we use the index stored in miniVals to access the corresponding element in st.

Code:

class MinStack {
public:
    vector<int> st;
    vector<int> miniVals;
    MinStack() {
    }

    void push(int val) {
        if(miniVals.empty() || val < st[miniVals.back()]){
            miniVals.push_back(st.size());
        }
        st.push_back(val);
    }

    void pop() {
        st.pop_back();
        if(miniVals.back() == st.size()) miniVals.pop_back();

    }

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

    int getMin() {
        return st[miniVals.back()];
    }
};

/**
 * 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();
 */

Time and Space Complexity

• Time Complexity: Each of the operations (push, pop, top, and getMin) takes constant time, O(1), as we are only performing basic vector operations, which have constant time complexity.

• Space Complexity: The space complexity is O(N), where N is the number of elements stored in the stack. This space is used to store the actual elements in st and the indices of minimum elements in miniVals.