L4. Implement Min Stack | Stack and Queue Playlist

[@devjindal8309]

Dangerous question with mind blowing explanation ❤

[@kamalesh4904]

For the optimal approach Use Long datatype for stack and min to pass edge cases as int may overflow when we multiply it by 2

[@studystuff51]

need to use long long, and nice DP btw

[@kamalesh4904]

@@studystuff51 thank you :)

[@rudrajitgupta3688]

Thank you striver for the intuition. I tried to implement the min stack using DLL where node represents (val,min,next,prev) all in O(1) optn push and pop represents addFirst remove first, and top will always hold min

[@rudrajitgupta3688]

class Data{ int val; int min; Data next; Data prev; Data(int val, int min){ this.val=val; this.min = min; this.prev=null; this.next=null; } } class MinStack { int min; Data head; Data tail; public MinStack() { this.min= Integer.MAX_VALUE; this.head = new Data(-1, min); this.tail = new Data(-1,min); this.head.next = this.tail; this.tail.prev = this.head; } public void push(int val) { // Data node = new Data(val, this.min); if(this.head.next == this.tail){ min = val; Data node = new Data(val,min); add(node); return; } min = Math.min(val, this.head.next.min);//-2, -3 Data node = new Data(val, min); add(node); } //(-3,-3),(0,-2),(-2,-2); //min = -3 public void pop() { remove(this.head.next); //min = this.head.next.min; } public int top() { return this.head.next.val; } public int getMin() { return this.head.next.min; } public void add(Data node){ Data next = this.head.next;// -1 ->20->-1 node.next= next; next.prev=node; node.prev=this.head; this.head.next=node; } public void remove(Data node){ //-1->10->20->-1 Data next= node.next; //20 this.head.next= next; next.prev = this.head; node.next=null; node.prev=null; } } /** * 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(); */

[@MohdYaqoob-s3k]

took me 1 hour to understand this code. This is awesome. The equation is just 🔥🔥🔥🔥🔥🔥

[@Dhruv-od3tc]

for all those who failed at 28th test case this worked for me use long instead of int and while returing do typecast

[@piyushmahale9024]

30% Completed till now ✅✅

[@JunaidShareef-j4u]

it has given medium level LC but i think it is harder to understand until striver comes here to understand us

[@ItsHarsh18]

watched for ig two or three times finally got it !!

[@IamNikhil2121]

timestamps 0:00 - Question Overview 1:45 - brute force solving Approach 4:34 - brute force pseudocode 6:50 - Brute force Time Complexity analysis 7:15 - Optimal solving approach 15:06 -Optimal pseudocode 19:38 - Time Complexity of Optimal 20:34 - Outro

[@ritikshandilya7075]

Thankyou so much Striver for great explanation

[@tilu391]

we can just use a variable which stores minimum element ,before every push , we can compare and update accordingly and while popping if we are popping min element , then we can traverse to find the min element...

[@kishoregowda8210]

Since we are trying to achieve getMin in O(1), this approach would not work.

[@apmotivationakashparmar722]

Thank you so much for this explaination. I am following your A-Z sheet . Can you please upload videos of left Question in A-Z sheet and Article as well .

[@Rahul-jr4gf]

Thank you so much for amazing explanation

[@theinsidestory8973]

00:04 Design a minimum stack that includes get min operation 02:41 Implementing Min Stack by tracking current minimum value while pushing elements. 05:00 Implementing a min stack with push, pop, and getMin operations 07:30 Implementing Min Stack using a simple stack and integer max as placeholder. 09:57 Implementing Min Stack involves inserting modified values and updating the minimum. 12:26 Modify minimum value in Min Stack implementation 15:14 Designing a minimum stack by implementing push and pop operations 17:44 Implementing Min Stack in a Stack structure 19:58 Implementing Min Stack with optimized approach

[@oyeesharme]

thank you bhaiya

[@radhepatel6876]

For the Second method consider this code as the TUF website's code is generating wrong output for A edge test case class MinStack { Stack st = new Stack(); Long min; public MinStack(){ min = Long.MAX_VALUE; } public void push(int val) { Long value = Long.valueOf(val); if(st.isEmpty()){ min = value; st.push(value); } else{ if(value>min){ st.push(value); } else{ st.push(2*value-min); min=value; } } } public void pop() { if(st.isEmpty()){ return; } Long val = st.pop(); if(val

[@RajChaturvedi-s1r]

at 4:35 if a interviewer ask us to design a stack we can design it using linked but after designing how we can use in this solution like out of class..

[@sahilmujawar8217]

understood ❤

[@sauravfarkade1928]

Understood!!

[@prabhakaran5542]

Understood ❤

[@jaydeeppatidar4189]

When heap playlist will be launched on youtube?

[@roiyaruryuga5183]

Hello Striver, We really want you to take rest. You have been working really hard lately.

[@mrrealnobody4382]

Striver means hardwork

[@PabitraPadhy]

you look for yourself first. nothing's gonna happen with flattering.

[@KartikeyTT]

tysm sir

[@sanketatmaram]

Great!

[@ushibuii8702]

wow got lucky, thanks for uploading

[@DeadPoolx1712]

UNDERSTOOD;

[@namannema3349]

op video and explanation

[@AkashkumarYadav-r4b]

Nice

[@priyaanshusoni]

His expressions at 12:56 😂😂😂😂

[@Shivi32590]

understood

[@SibiRanganathL]

Understood

[@pBERA0_0]

couldnt understand intuition behind 2*val-min at all.

[@crazymemes4080]

btw now i got it why striver bhaya is not providing code in the video :) so that we check the website too 😄 damn 6 star coder

[@hashcodez757]

Thanks alot Bhaiya!! Understood

[@THOSHI-cn6hg]

bro looks tired

[@SunnyKumar-dw9ze]

Why multiplication with 2

[@prathameshjadhav2942]

Very low energy #striver_79

[@vinit_notfound]

❤❤❤

[@shiva.g1898]

👍👍

[@varunsingh8322]

lesgoogogogoog

[@anikbiswas8]

only 22 testcases passed using second method

[@Surya-teja2612]

How about in first method

[@worldfacts6760]

@@Surya-teja2612 all text case will pass

[@yatharthgupta6468]

use ll

[@yatharthgupta6468]

#define ll long long class MinStack { public: stack st; ll min; MinStack() {} void push(int val) { if(st.empty()) { st.push(val); min = val; } else { if(val < min) { st.push(2ll * val - min); min = val; } else { st.push(val); } } } void pop() { ll top = st.top(); if(top < min) { min = 2ll * min - top; } st.pop(); } int top() { ll top = st.top(); if(top < min) { return min; } else { return top; } } int getMin() { return min; } }; /** * 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(); */

[@crazymemes4080]

understood sirrrr

[@harshuke5831]

Understood ❤

[@lokesh8660]

Nice