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 elementval
onto the stack. -
void pop()
removes the element on thetop
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
andminiVals
, 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 ontominiVals
. 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 fromst
. If the index of the minimum element (miniVals.back()
) matches the index of the element being removed, we also remove it fromminiVals
.Retrieving the top element (
top()
) is straightforward; we return the last element ofst
.To get the minimum element (
getMin()
), we use the index stored inminiVals
to access the corresponding element inst
.
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
, andgetMin
) 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 inminiVals
.
Top comments (0)