Design Min Stack - Amazon Interview Question - Leetcode 155 - Python

[@TechDevNick]

It's so amazing how simple a problem looks when you get to understand the tricky part

[@AndreiSokolov-k7j]

The devil is in the details

[@AndreiSokolov-k7j]

but also "the crest wasn’t hard to open"

[@josephjoestar4318]

Friends, If you use a Linked List it won't have to reallocate when the array reaches it's limit and you can push the min value into the nodes, so head node always have the min. Love your work NeetCode. Even if I nail the answer, I always check your solution and I learn something, even if it's just syntax tricks.

[@namelesss8226]

What do you mean, could you explain a bit more?

[@josephjoestar4318]

@@namelesss8226 Sorry I don't have the brain power to go through this video currently. But based on past me's comment, arrays are stored in memory as one block, when you add to it, behind the scenes, it creates a new array with the new length and copies over the values. Some languages when creating arrays, block out extra space in the case it expands. Linked lists don't have this issue since they aren't stored as one block in memory.

[@ThePacemaker45]

I love how the name of the problem itself is actually the biggest hint.

[@ladydimitrescu1155]

omg just noticed that

[@stylisgames]

Only those who have already solved the problem will get it IMO the actual hint on Leetcode is much better

[@dollyvishwakarma2]

Nice explanation. How I solved it was modifying the structure of the stack itself, i.e an element of the stack can be a pair of val and min so far: class MinStack: def __init__(self): self.stack = [] def push(self, val: int) -> None: self.stack.append((val, min(val, self.stack[-1][1] if self.stack else val))) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()

[@hamoodhabibi7026]

Nice! I did it using tuples instead but same it's the same code structure

[@kofinartey6348]

I did it using a hash map / dictionary for each element of the stack containing both values for the min and the current value. I think this is also a good alternative

[@jorgealbertorun]

I did it this way too! Seemed more intuitive

[@KermitDominicano]

I did it like this too

[@niksintelli]

Hi NeetCode, I know this is kind of a simple problem but I started recently watching your videos and I did this problem on my own just by seeing your explanation! Thank you so much, keep up the good work

[@NeetCode]

That's awesome! Appreciate the kind words!

[@Vaibhav-h5p]

Same for me! It's so fun watching these videos. And being able to solve the problems without looking at the code is such a good feeling.

[@cp65143]

X. X

[@sevenscapes]

Your way of looking at the problem, effectively simplifies the problem statement. Love your approach!💯

[@aldolunabueno2634]

I'm glad I resisted the urge to see the solution, because I really enjoyed getting to the solution from the hint alone. Thanks!

[@licokr]

Thanks for the video. I don't know why but I thought I had to store them as indexes and you know, as it pushes and pops, the index can be different. While watching your videos, I've got to able to stay away from fixed ideas I've had. Surely, solving coding problems is way beyond just coding, memorizing and knowing algorithm or datastructure. thanks a lot Neetcode!

[@krishnaharshith9854]

Just made a small mistake and I realized it after watching your video sir, Excellent explanation, thank you sir🙏

[@KermitDominicano]

The hint made this so much easier. Instant realization lol

[@venkatasundararaman]

I feel we can have a single stack containing a tuple class MinStack: def __init__(self): self.minStack = [] def push(self, val: int) -> None: minVal = min(val, self.minStack[-1][1] if self.minStack else val) self.minStack.append((val, minVal)) def pop(self) -> None: self.minStack.pop() def top(self) -> int: return self.minStack[-1][0] if self.minStack else None def getMin(self) -> int: return self.minStack[-1][1] if self.minStack else None

[@khappekhappe133]

new to python; how would you write this without the list comprehension way?

[@expansivegymnast1020]

This is actually a pretty decent way of doing it.

[@floydian25]

nice solution

[@ridhawritescode]

@@khappekhappe133 There are no list comprehensions here. You may be thinking of how he used pythons "lambdas." When he says "self.minStack[-1][1] if self.minStack else val" for example. That essentially means if the minStack exists, use that value, otherwise use val. In many other languages it would look more like this "self.minStack ? self.minStack[-1][1] : val." He does the same thing on top and getMin, he doesn't need to since these functions will never be called on an empty stack, but just in case I guess. Hope that helps.

[@akm1237]

its the same memory

[@stylisgames]

See I was solving this problem on the actual neetcode website which does not have the hint about each node in the stack having a minimum value. That hint was all I needed, I actually solved it on my own with that! Would be great if the site included any hints that are on Leetcode.

[@CST1992]

Instead of using two stacks, you can also use a single stack which contains tuples of the current and minimum values as explained in the video. I've tried it and it works the same way.

[@anonimettalontana4944]

Interesting and a lot simpler than my implementation! What I did was to keep an array for getting the most recent element and a double linked list for getting the minimum, which is stored right after the dummy head.

[@gnes04]

Leetcode updated this from an easy to medium level lol

[@syafzal273]

Your implementation is super clean, I tried adding tuples to a list with the current and current min values but having 2 stacks is so much cleaner IMO

[@deepak655655]

instead of two stack , we can have a single stack with , list of 2 values instead of integer. At index 0 we can store the value and at index 1 we can store minimum till that point.

[@prajjwaldubey5787]

Yes we can do this too. good observation. I have implemented it take a look:- class MinStack: def __init__(self): self.stack=[] def push(self, val: int) -> None: if not self.stack: self.stack.append([val,val]) else: if self.stack[-1][1] > val: self.stack.append([val,val]) else: self.stack.append([val,self.stack[-1][1]]) return self.stack def pop(self) -> None: return self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]

[@ninjaturtle205]

This is how I did. Slightly different than neetcode. The minimums stack is only updated when the most minimum is pushed onto the minStack. class MinStack: def __init__(self): self.stack = [] self.minimums = [] def push(self, a): self.stack.append(a) if len(self.minimums)==0: self.minimums.append(a) elif a int: return self.minimums[-1] def top(self) -> int: return self.stack[-1]

[@danny65769]

I did something similar, but storing the indices in the minimums stack. In your solution, a new value should still be stored if it equals to (not only less than) self.minimums[-1], otherwise it won't work if there are duplicate minimums. This approach is similar to using a monotonic decreasing stack, except that we don't need to pop smaller values when adding a new value - we just don't add the value to the minimums stack at all if the new value is greater than minimums[-1].

[@someone3706]

@@danny65769 I did the same way as you said, I forget the equal sign first but I got there eventually. And this was 2x faster than the video solution. Is it because we didn't append the min everytime when it is the same min?

[@sondolkin]

This is the solution I had as well. Was checking the comments to see if others arrived at the same solution. Nice.

[@swarupsaha9064]

If every guy working in FAANG is as much talented as he is, we are so F**** up. Thanks NeetCode For your knowledge. Love from India

[@jasonswift7468]

In java. for pop() method. We should notice the below. == to determine whether the object is the same (memory address), and equals to determine whether two objects are the same. String a = new String("abc"); String b = new String("abc"); String c = a; System.out.println(a == b); // false System.out.println(a == c); // true System.out.println(a.equals(b)); // true System.out.println(a.equals(c)); // true

[@dhruvsolanki4473]

Currently it is rated as Medium.

[@RandomShowerThoughts]

the hint from leetcode was truly amazing tbh

[@RM-xr8lq]

this strategy is called 'augmented data structure'

[@devenlad]

Thanks for pointing out hint. As soon as I saw hint, problem was solved in my head.

[@shreyaschaudhary-r6d]

I could never think of such an approach. Thank you!

[@mangalegends]

Looks like they upgraded this question to a medium. And your solution is better than mine lol, I used a stack and a heap but 2 stacks is simpler

[@LeetCodeSimplified]

I also thought of implementing a heap but since pushing new elements onto the heap wouldn't have been O(1), I knew that they were looking for a different solution haha

[@symbol767]

This is marked as "easy" jeez, that O(1) Time complexity makes it medium at least

[@At-oc3lq]

right!?!? It took me a minute to realize what I had to do for constant time.

[@minciNashu]

it was changed to a medium

[@aaqibjavedz2569]

Took me more that a min. I used a array list instead of a stack for the minStack

[@lakewobegonesbest8725]

It’s a Medium now. But it’s bizarre that this was Easy while #50 Pow(x,n) is (still) listed as Medium! For Py/Java/JS, #50 is the easiest I’ve seen.

[@EE12345]

its medium now. first time seeing them raise the difficulty tag on a problem, I thought the problems only get harder over time so mediums become easys

[@ahmedanwer6899]

interesting how we cover for the case where the minValue is duplicated in the stack. but leetcode doesnt test that and so if you use just a single variable to hold the min value and like not even update it when the minvalue is poppped, the tests still pass. it also doesn't test duplicate mmin values at all. idek if im making sense. however, the above solution yields slower runtime in leetcode

[@inarizakiFan]

OMG, I did get the idea to store the min values as well, but for some reason, I created two extra stacks. One for storing the current minimum one for storing the last minimum, and, if I'd just taken a step back, I'd have realized how utterly un-needed that was. That's the kind of shit your brain will come up with when you're tired.

[@visuality2541]

really nice, particularly how the minStack works here.

[@Akhil-yy3ip]

class MinStack: def __init__(self): self.arr = [] def push(self, val: int) -> None: self.arr.append(val) def pop(self) -> None: self.arr.pop() def top(self) -> int: return self.arr[-1] def getMin(self) -> int: return min(self.arr)

[@hugenerretho9151]

its o(n) time complexity for min function so doesnt work

[@hamza-chaudhry]

7:36 That's why I used an ArrayList (in Java) so had to write all the functions manually 7:50 8:06 How do you know that? 8:12 Yeah I was confused but don't use Python anyway

[@hamza-chaudhry]

5:33

[@thehomiebearfifa3528]

I'm confused about the pop function. If we pop from the regular stack, why is that equivalent to popping from the minStack? On the first stack, we're removing the top most element (which could be any number), while we also removing the top most element from the min stack which is which is not necessarily the same element? Let's say we add -1 to the stack, while the least number is currently -3, in that case we don't append -1 to the top of the minStack, but we do add it to the regular stack. When we go to pop, we pop both elements (-3 from the minStack, and -1 from the regular stack)?

[@hoixthegreat8359]

The minStack contains the minimum element at that time-every time we add something to the stack, we add the minimum element (incl. the new addition) to the minStack, so they are always the same length. It might click in your head a lot better if you work through the code with an example array input. E.g. look at your example (say arr = [1, 10, -3, -1]) push 1: stack = [1], minStack = [1] push 2: stack = [1, 10], minStack = [1, 1] push 3: stack = [1, 10, -3], minStack = [1, 1, -3] push 4: stack = [1, 10, -3, -1], minStack = [1, 1, -3, -3]

[@chayex1814]

Why not implement a normal stack class and use the min() function in getMin(self) like this: "class MinStack: def __init__(self): self.stack = [] def push(self, val: int) -> None: self.stack.append(val) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return min(self.stack)"?

[@sergiofranklin8809]

here it's asked to have O(1) in all operations, and we are using array, so in that case push/pop operations' complexity is amortized O(1), which means sometimes it'll take O(n) time. So, solution breaks this requirement isn't it? if not, please someone explain

[@yskida5]

Isn't the worst-case for both of these O(1)? Why would it take O(n)

[@RM-xr8lq]

​@@bensinger5897 inserting into dynamic array is O(n) worst case for whenever the array needs to expand, and copy over its elements to a new block of memory (here the stack is implemented with a list/dynamic array) since that doesn't happen often (only when array not big enough), the amortized time complexity is O(1)

[@bensinger5897]

@@RM-xr8lq Thats right, I deleted my comment

[@randomystick]

@@RM-xr8lq think that's an OS/hardware concern and not an algorithm concern which is what the interviewers are looking for, though I wager mentioning it at the end of the interview would be a plus point

[@Shivam-yy8qe]

thanks nice exaplinations. we can also do this using only one stack using pairs . In first we keep actual value,and in second we store the minimum till that element

[@mr_noob6361]

Your logic building is fabulous..how u r doing this Mann😑😑😑 thats the reason u r in Google and i am still unemployed...sir it's my humble req please provide python and DSA tutorials for free😔😔👏👏

[@zehbarrayani7215]

Seriously the best

[@Rohit-qp1ye]

Add this to stack playlist

[@AlexanderLopez-yx4ck]

wow im over here thinking i had to make a stack class from scratch with a node class and everything lmao

[@noufbouf]

I feel like my code is ridiculously simple and it passed the leetcode test. I am doing something wrong? class MinStack: def __init__(self): self.l = [] def push(self, val: int) -> None: self.l.append(val) def pop(self) -> None: del self.l[-1] def top(self) -> int: return self.l[-1] def getMin(self) -> int: return min(self.l)

[@abeizify]

getMin is O(n) in worst case, but the code from the video is O(1)

[@mrditkovich2339]

Without extra space, the intuition is like : When we are popping a value from stack, if it is the minimum, then we need to know the minimum of remaining numbers. Can we try to adjust this in the same stack instead of a separate min stack ? yes, we can ensure this by pushing an extra value While pushing, we will check if the element we are pushing is less than minimum, in this case, we have to push the existing min number and then the new number. After this, our new number becomes the updated minimum. Now while popping, If we are popping the number and it is min, we pop an extra value out of the stack, this extra becomes the updated minimum.

[@minciNashu]

you actually do it by pushing differences, instead of actual values, for new minimums

[@nos44-]

How is that any different form taking two stacks .. you are occupying the same. Space !! Isn't it... You are increasing the size of this array ... Instead of taking a separate one ... 😶

[@koushika4855]

Is there any way we can support all the operations by using O(1) space and time? Thanks!

[@xedose7183]

Nice Explanation

[@pabloj1336]

Any other examples of your syntax from line 10?

[@mohitpatil6689]

I guess there is some Problem in the code while submitting if Minstack() is called on the first call then we couldn't return anything and the test case fail, IDK you have tackle this problme or not but I have got this problem. :)

[@souljarohill8795]

leetcode is so weird. some mediums like this one are way easier than some easy problems lol

[@СергейВоробьёв-ы5л8б]

I am more on java and c++ but am I right that technically [] in python is a structure that will grow with specific coef, creating new array and refill it by existing items every time it goes to limit and newer become smaller?

[@anshukkl3300]

why can't you use self.q=deque() method here? Do we necessarily need two stacks initialization ? ``` class MinStack(object): def __init__(self): self.q=deque() def push(self, val): """ :type val: int :rtype: None """ self.q.append(val) def pop(self): """ :rtype: None """ for i in range(len(self.q)-1): self.push(self.q.popleft()) return self.q.popleft() def top(self): """ :rtype: int """ return self.q[-1] def getMin(self): """ :rtype: int """ min=self.q[-1] for i in range(len(self.q)): if self.q[i]

[@florin-alexandrustanciu5643]

Wouldn t it be better with a new Node class that has a value and a min? This way you dont store twice the number of pointers

[@inarizakiFan]

But you do store them in the node class right? (for each node you have two variables to store the element and min)? Why would it be better?

[@mnchester]

This is a Medium now

[@mokshcodes]

Why do you need a stack to keep track of the minimum, can't you just set a min variable m to min(m, currVal)

[@OwenWu-f9t]

why can't we do return self.stack.pop() instead of return self.stack[-1]?

[@weaammohamed8992]

Great explanation!

[@sunshineandrainbow5453]

Please tell how to do it with O(1) space complexity.

[@itdepends5906]

Awesome clear video :)

[@asdfasyakitori8514]

This is so clever

[@ruiqiyin3847]

You made it so easy! Could you do Max Stack too?

[@darthvadar2915]

It’s literally the reverse

[@martinemanuel8239]

I'ts a perfect exercise to implement your own stack to :P

[@vikasgupta1828]

Thanks

[@sanooosai]

thnak you sir

[@shawnlu7830]

how about we just use the built in min() function in python to get the min value, this way we dont need another stack, so it saves some space

[@spaghettiking653]

This is true, but min() goes over the whole stack in order to calculate the min, so this takes O(n) and it needs to be O(1) for the solution to be accepted.

[@kofinartey6348]

Hi Neetcode … great video 😊😊.. but I’m thinking of an edge case here. What will happen if the getMin() or top() functions are called on an empty stack. From your implementation I think it would throw an error which would be “list index out of range”. So would it be better to put a check with the return statement of those functions to prevent those errors?

[@NeetCode]

Yeah good point, in this case I think we're guaranteed no invalid calls will be made, but in a real interview your point would be good to ask.

[@ssuriset]

"Consider each node in the stack having a minimum value." How is a normal person supposed to understand this?

[@e555t66]

Neat.

[@juliuscecilia6005]

Neet*

[@lakewobegonesbest8725]

I looked at this problem yesterday and it was listed as Medium.

[@yy-ll1uw]

So elegant

[@wybsl5087]

This question is medium now 🧐

[@bashaarshah2974]

Doesn't utilizing the min function on line 10 make the run time for that method O(n)?

[@AustinCS]

no

[@hambroman]

the thumbnail for this is a spoiler lol

[@DeveloperCoder]

MinStack Java Solution: kzbin.info/www/bejne/onncn4Sqf7qWjtU

[@jinwoopark755]

Can you do accounts merge explanation please?

[@CEOofTheHood]

i feel like this is a terrible interview question. You just need to know the trick and question solves itself

[@abhishekshah4443]

Pretty much all the coding interview rounds and their questions are like that (which is still a terrible thing)

[@mikaylatheengineer9631]

isn't that all tech interview questions?

[@CEOofTheHood]

@@mikaylatheengineer9631 no some require mental application

[@motivewave001]

@@CEOofTheHood only when you don’t know the tricks

[@austinchettiar6784]

@@motivewave001 what is the space complexity? is it 2n? can anyone tell

[@bestsaurabh]

If this is tricky, I am just wondering how tricky it is to do this without using any extra space??! I

[@minciNashu]

store differences

[@tivialvarez]

probably have moved on but I just found a video with a pretty clever solution kzbin.info/www/bejne/jGGcf5mXfMtll9E

[@misteryue2739]

I don't really get the pop() function, doesn't it need a condition check before pop()ing out off the minStack ?

[@Senzatie160]

Nope, why? Every time you pop an element off the stack, you also pop the min at that level from the minStack.

[@misteryue2739]

@@Senzatie160 Right, I didn't catch the fact the minStack represented the current minimum so I got confused. So much info when trying to learn algos, I was overwhelmed haha

[@demdimi9316]

@@Senzatie160 thnx lol

[@iIrfanhussain]

We can do this qn by O(N) space but it's super hard

[@inarizakiFan]

for O(n) you'd traverse the elements, which wouldn't really work if the data structure is a proper stack since you can only access the top value. You could do it in a clumsy way by popping from a copy stack to traverse though.

[@dhelmy]

Doomed enterprises divide lives forever into the then and the now.

[@programming3043]

Done

[@TOn-fx2gr]

You have a bug in the pop method of your minstack class

[@swaroopkv4540]

Y pop from both stack

[@jewsefjones]

Pop returning none irks me

[@tsunningwah3471]

斤斤計較

[@АльбусДамблодр]

i love u

[@aabhishek4911]

does python not have an inbuilt stack ? feel like you using an array for these stack problems kind of weird.

[@minciNashu]

thats technically a list, but even so, for example the C++ vector can do push and pop

[@SuubUWU]

Technically the problem is asking you to "design" a min stack. In real-life coding interviews, it honestly depends on the interviewer. Some will let it slide because they don't expect you to write your own min stack structure. Others will see it as a potential crutch because you couldn't demonstrate that you could design it. It's good to know built-in language libraries to save time when they're allowed but only if you understand how to design them from scratch once you're 3~6 interviews in. They have to start finding reasons to disqualify you from other candidates. The best practice here is to simply ask if you can use a standard library.

[@jonaskhanwald566]

576. Out of Boundary Paths. Do a video on this