DAY 105 - 155. Min Stack
Tags: leetcode, coding, algorithms, codenewbie
Published: 2023-09-16 13:48:52

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](https://leetcode.com/problems/min-stack/description/)

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:

```cpp

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`.