155. Min Stack Leetcode Solution
Min Stack Leetcode Problem :
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.
Min Stack Leetcode Solution :
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.
Intuition :
The MinStack class is designed to maintain a stack of elements while also keeping track of the minimum element in the stack.
Approach :
1. The MinStack class uses a single stack, stk, to store pairs of elements and the minimum values encountered so far.
2: When an element is pushed onto the stack, the current minimum value is calculated by comparing the new element with the minimum value stored on top of the stack. The pair (element, current minimum) is then pushed onto the stack.
3: When an element is popped from the stack, it effectively removes the top pair, effectively reverting to the previous state.
4: The top function returns the first element of the top pair on the stack, and the getMin function returns the second element of the top pair, which represents the current minimum value.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class MinStack {
public:
typedef struct node{
int v;
int minUntilNow;
node* next;
}node;
MinStack() : topN(nullptr){
}
void push(int val) {
node* n = new node;
n->v = n->minUntilNow = val;
n->next = nullptr;
if(topN == nullptr){
topN = n;
}
else{
n->minUntilNow = min(n->v,topN->minUntilNow);
n->next = topN;
topN = n;
}
}
void pop() {
topN = topN->next;
}
int top() {
return topN->v;
}
int getMin() {
return topN->minUntilNow;
}
private:
node* topN;
};
class MinStack {
LinkedList< TplusMin> stack;
private class TplusMin {
int val;
int min;
public TplusMin(int val, int min) {
this.val = val;
this.min = min;
}
}
public MinStack() {
stack = new LinkedList<>();
}
public void push(int val) {
int newMin;
if (stack.size() == 0){
newMin = val;
}
else {
int currentMin = stack.getFirst().min;
newMin = val < currentMin ? val : currentMin;
}
stack.addFirst(new TplusMin(val, newMin));
}
public void pop() {
stack.removeFirst();
}
public int top() {
return stack.peekFirst().val;
}
public int getMin() {
return stack.peekFirst().min;
}
}
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
if self.minStack:
val = min(self.minStack[-1],val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment