Implement min stack | Leetcode #155

This video explains how to implement a stack with get minimum operation in just O(1) time. This video explains how to implement getmin(), top(), push(), pop() in constant time O(1). You can also implement max stack in the same way as min stack. I have explained using a simple example and have also explained the code for the same. As usual, CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[crimsoncad]

Little space optimization can be done here.
Just don't push the same minimum value for every value in stack. Just push the minimum value once and if the occuring number is greater than min then just push the value in the stack but don't push the minimum value again.
Whenever you pop a value, just check
If the value at top of stack is equal to value at top of min stack.
Then pop both; the stack top and the min top.
Else just pop from stack.

[spetsnaz_]

Saw your video on this topic earlier, so solved it easily 👍

[sa]

Thanks techdose for the amazing tutorial .Your videos motivates and guides us in every aspect of DSA learning😁

[ankitkumarmishra]

Space optimized approach:

class MinStack {
private:
vector<pair<int, int>> minStack;
public:
MinStack() {}
void push(int x) {
if(minStack.empty()) minStack.emplace_back(x, x);
else minStack.emplace_back(x, min(minStack.back().second, x));
}
void pop() {
minStack.pop_back();
}
int top() {
return minStack.back().first;
}
int getMin() {
return minStack.back().second;
}
};

[Rahul-rphk]

You had put a video on this using O(1) space before and i tried using it in the leetcode challenge but it didnt pass the second last test case. Can you please try it and help us with the code or a video if it works for you. Thank you sir, your videos help me learn a lot

[rajeshbammidy]

A much-optimized approach with considerably less space:
class MinStack {
Stack<Integer> stack;
Stack<Integer> minS;

public MinStack() {
stack = new Stack<>();
minS = new Stack<>();
}

public void push(int x) {

if (stack.isEmpty()) {
stack.push(x);
minS.push(x);
} else {
stack.push(x);
if (x <= minS.peek()) minS.push(x);
}
}

public void pop() {
int sp = stack.peek();
int mp = minS.peek();
if (sp == mp) {
stack.pop();
minS.pop();
} else {
stack.pop();
}


}

public int top() {
return stack.peek();
}

public int getMin() {
return minS.peek();
}
}

[retrogame]

bhai amount of rain water trap ki problem solve kro
i think very popular problem

[glazedsn]

Further space optimization is using (min, count) for each element in the min element stack. When you reach an element < min, then push it with count 1; if equal, increment; otherwise nothing. Then when popping the stack, you either decrement count (equal to min elt and count > 1) or pop the min stack (equal to min elt and count == 1). Slightly slower than just pushing the value from normal stack to the min stack when it's <= the last element in the min stack (due to extra comparisons of == vs > and using multidimensional array), but saves space in the cases where you are pushing the same element (current min) over and over again to the min stack.

[NikhilKumar-oymx]

i am unable to understand how int array will take string as input. I tried using vector and used library functions but in a testcase there were input including both string and int value. if you could help??

[Axfa]

bro nice content, but have more emotion in speaking dude, otherwise you sound very monotone