Implement Min Stack | O(2N) and O(N) Space Complexity

[@takeUforward]

Please like the video, helps a lot :) Also please spare a second to drop in a comment if you understood or not ..

[@shwetanksingh5208]

Hey brother....int take 4bytes and long takes 8bytes.....so it is not the case that your second approach saves space.....I have verified it by submitting both solution on leetcode too......following is the code for first approach class MinStack { public: stack stac;// MinStack() { } void push(int val) { if(stac.empty()) { stac.push(make_pair(val,val));//if stack is empty then the value being pushed will also be minimum itself } else { stac.push(make_pair(val,min(val,stac.top().second)));//minimum value will be minimum of minimum till here and this value } } void pop() { stac.pop(); } int top() { return stac.top().first; } int getMin() { return stac.top().second; } };

[@shra1]

In line no. 34, can we not reduce equation to "mini = elem;" (algebraically) ?

[@artofwrick]

The question had become medium in leetcode. Ahahahaha😂

[@muhammedimdaad]

amazing, but the question that I am having is, how in the world one can come across the idea for O(N)? like, that's tough to just think and come at the first place !!

[@mouthearnose]

Yeah these kind of questions are hard to think of during the interview if you haven't done these before.

[@deepanshudahiya8966]

almost did the question but the pair thing wasnt able to think abouti it and when striver started he just made me clear about the concept

[@shuvbhowmickbestin]

the level shouldn't be easy when asked to implement the solution at O(1) extra space. It should rather be medium/hard.

[@rupamrai9455]

657 views and only 74 likes please each and everyone like and share this Precious content. Thanks, striver for your time and effort

[@tulika2863]

Thank you , thank you so much for putting your efforts and this kind of high quality content . 🙏🏽🥺

[@ytg6663]

🥺🥺

[@producer_6_1_musics13]

encoded_value=2 * new_minimum - old_minimum old_minimum=2 * current_minimum - encoded_value...this generalization helped me a lot,

[@shivalikagupta3433]

Thank youu sooo much !!! this ques came in one of my friend's interview, mine is near and here I am clearing the concepts.

[@madhu_mohanreddy]

and?

[@shantanugupta-oz1dx]

Thank you so much for explaining all the problems so well. Very helpful thank you so much again

[@atharvacodes3705]

Finally understood after watching 2 times and dry running. Keep up the good work! :)

[@vaalarivan_p]

but doesnt using a stack consume as much memory as using stack since the former is 64 bits?

[@bhavyramani4456]

you seriously think that pair is O(2*n) and long long int is O(n) than it does not make sense logically, because long long occupies twice memory than normal int, and if contraints were from int64_min, int64_max than you can never use second approach, so you can not say that 2nd approach is better than first one. Still 2nd approcah was very nice i am not completely against it.

[@rutuja7293]

Amazing and fruitful as always.Thank you for your efforts.

[@joshipratik232]

Here is simple logic. //Time Complexity for each function is O(1). class MinStack { public: pair st[30000]; int t,min; MinStack() { t=-1; min=INT_MAX; } void push(int val) { if(t==-1 || val

[@rohan8758]

Unbelievable explanation for modified value to be pushed into the stack & rollBack to prevMinimal value! Hey Striver How much good you are in mathematics at your school time or have you studied higher algorithmic mathematics like usually Famour algorithian has gone through that content once in their life.

[@artofwrick]

For leetcode, the answer wouldn't come at edge if you multiply with 2. Instead use add like min=min-st.peek()+min;

[@manojnavinjamuri5867]

Thank you soo much. This helped me to think the solution in different perspective.

[@sayanmukherjee8563]

Thank you so much for the great, simple and clear explanation.

[@stith_pragya]

Understood.............Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@aditi1729]

why are we storing modified value in the stack?

[@manaswitadatta]

Finally understood the proof clearly. Ty :)

[@tivialvarez]

How were you able to come up with a formula that always ensured the result would be smaller than the minimum value? I can understand solutions like this but I don't understand how you were able to find such patterns sometimes. Were there any mathematical rules you used? I know that one important part was that you included the previous minimum in the calculation so that you are able to derive it from the stack value later when popping. How did you even get the idea to encode the previous minimum into the stack value to begin with? I find these kinds of discussions much more interesting and helpful to learners than just simply showing solutions, although its appreciated.

[@tivialvarez]

I guess one kind of intuition that could be used is: if we want to store extra information/data without using extra memory, we should look for places in the existing memory we're using to sneak in some extra information. For example assuming that all JavaScript numbers are 64-bits and our range of numbers is small, then we'll never use or overflow the full 64 bits (although it is something to be wary of.) So in some of those unused bits we can store that extra data as long as we can consistently undo and redo whatever we did to regain the original value. This also only works because a manipulation of the stack value means the min value has changed, and the only time the min value changes is when the stack value is manipulated. Therefore, whenever the stack value is not what we expect it to be, the min value has to be the value that the stack was "supposed" to be. That value is also necessary to get back the value of the previous minimum. I'd still love to hear the thought process on how you came up with a "function" that reliably returned a value smaller than the min value for that comparison though.

[@artofwrick]

Arithmetic Progression

[@albedo9617]

If we add -2 to the stack, pop it and then try to access the value of minimum, it will return as 2, but shouldn't it return us 0 or nothing in this case?

[@freshcontent3729]

bhaiya placements are starting, please upload many videos, go on full speed uploading ! :)

[@AngadSingh97]

I am now having a great time solving problems everyday, wow

[@aashishmittal79]

Isn't the optimal solution O(2N) space as well because we are using long long which is double the size of int datatype?

[@artofwrick]

Yess. Infact using pair class is safe

[@ashokdurunde1814]

Thank you , thank you so much for putting your efforts and this kind of high quality content . 🙏🏽

[@siddharth794]

This videos should be in stack playlist

[@Musicuvakavi1823]

Great teacher in the world

[@geekyNib]

Hey Striver ..I didn't get how this formula is derived ..like (2*current_min- earlier_min) while pushing..can't we use someother...?? Like not able to intuit it for O(2*N)->O(N)...

[@artofwrick]

min=min-st.peek()+min

[@scorcismweb5723]

2nd one is easy but im sure i wont be able to recall this

[@techbus6016]

If you are using long instead of int, you are already utilising double the space of elements, it's like instead of storing min separately in a int variable mini, you are storing same information in a long var. you are just widening the data type instead of using separate var, both solution will use the same space.There is no such optimization.

[@aakritisharma5220]

best teacher over youtube

[@naikajsevak6090]

can we do like this if we get val as min of minSoFar then we multiply the both number and store it modify value in stack and atlast whenever we the pop operation come we check if the minSofar is not equal to top of value of stack then we divide min value and get previous min am i right wrong please correct me if i have wrong

[@risingengineers]

i wish i can meet you one day bhaia.

[@vasujain1970]

Great video as usual brother, enjoy your content a lot! Keep up the good work!

[@sukhii0220]

Is no one concerned about it ? why we use formula in push opr 2*val-mini ? why we come with this ? please explain

[@MindsetMotivation75]

In O(2N) 2 is just a constant . So , why we are considering this ?

[@akash_assist]

because interviewer will ask you to optimize your code more and more......and you can't say no to the interviewer......if you say so.....he will just mark "not solved"......and you will get yourself rejected.

[@tivialvarez]

Constants rarely make a noticeable difference but they can sometimes. It's always just good to know anyways. If you have an O(N) vs an O(40N) solution with no other real difference why wouldn't you always prefer the O(N) solution? It may not be significantly or even noticeably faster, but it is in fact faster. Maybe even less complex.

[@Brute_Coder]

Here is the implementation of first method (sc -> O(2N) ) using Pair class in java.... // create a Pair class to store data and the min value encountered till then class Pair { int data; int min; public Pair(int _data, int _min) { this.data = _data; this.min = _min; } } class MinStack { Stack < Pair > stack; int minValue; public MinStack() { stack = new Stack < > (); minValue = Integer.MAX_VALUE; } public void push(int val) { if (val < minValue) minValue = val; // check if the value is lowest or not stack.push(new Pair(val, minValue)); } public void pop() { stack.pop(); if (!stack.isEmpty()) { minValue = stack.peek().min; } else { minValue = Integer.MAX_VALUE; // If the stack is empty, reset minValue to its initial value. } } public int top() { return stack.peek().data; } public int getMin() { return stack.peek().min; } }

[@Himanshu_Mahuri]

why you have not added the link of this video in sde sheet .bhaia give some time and please update links of sde sheet doc . it will be easier .

[@aashayagarwal8903]

why are we storing the modified value?? just store the original and take min?

[@gyaniyoda4608]

Time complexity will be O(n)

[@artofwrick]

Cuz... You'll lose track of which was the last min and which was even last everytime you pop...

[@Rahul_246a]

Wonderfully explained

[@Karan-vq5vg]

please update the link in the website

[@AmitSingh-ut4wt]

Really amazing approach

[@SaiTeja-ob6zg]

wonderful explaination brother!

[@adishijha8365]

Amazing explanation!

[@techwithindrani9376]

Great content, thanks much for your effort. 😊

[@_-6912]

I understood the solution but I guess link is not reflecting in SDE sheet!

[@takeUforward]

Forgot to add, will add it soon. Thanks.

[@_-6912]

@@takeUforward Thanks Raj 😊

[@sanskaarpatni9137]

Amazing as always!

[@AshishKumar-pq6pr]

Awesome lecture

[@codeman3828]

Crazy optimal solution

[@BECSAQUIB]

You did not tell the intution behind the logic. You just verified it.

[@vaalarivan_p]

5:15 - 7:55

[@nikhil_squats]

Please make tree series

[@stalker1164]

He is saying this 102th time that Tree series comes after 100k subscribers

[@rishabh6210]

how is it better if we end up taking long long T_T

[@ridj41]

2nd approach wasn't intuitutive at all.

[@SuperWhatusername]

understood Thanks

[@sanskarrawat1047]

indeed indeed indeed...

[@saouli1632]

thank you bhiya❤🙏

[@Learnprogramming-q7f]

Thank you Bhaiya

[@MJBZG]

v good

[@hitheshpk6030]

UNDERSTOOD

[@cypher7536]

Understood! 🔥

[@rishabhgautam7863]

Lol... maine do stacks se kiya tha ye phele hahaha

[@yushsingla9905]

understood

[@satvrii]

❤

[@abhishekpadhy903]

op explaination

[@Shivi32590]

thank you

[@kasyapdharanikota8570]

understood

[@roughuse.jaiganesh]

understood.

[@gaddamsaijyothi2659]

understood

[@tanishkumar6682]

understood