Design Min Stack - Amazon Interview Question - Leetcode 155 - Python
Vložit
- čas přidán 5. 08. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/minimum-...
0:00 - Read the problem
1:00 - Drawing Explanation
5:22 - Coding Explanation
leetcode 155
This question was identified as an amazon interview question from here: github.com/xizhengszhang/Leet...
#amazon #stack #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
It's so amazing how simple a problem looks when you get to understand the tricky part
The devil is in the details
but also "the crest wasn’t hard to open"
I love how the name of the problem itself is actually the biggest hint.
omg just noticed that
Only those who have already solved the problem will get it IMO the actual hint on Leetcode is much better
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.
Your way of looking at the problem, effectively simplifies the problem statement. Love your approach!💯
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()
Nice! I did it using tuples instead but same it's the same code structure
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
I did it this way too! Seemed more intuitive
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.
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
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!
I'm glad I resisted the urge to see the solution, because I really enjoyed getting to the solution from the hint alone. Thanks!
I could never think of such an approach. Thank you!
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
new to python; how would you write this without the list comprehension way?
This is actually a pretty decent way of doing it.
nice solution
@@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.
its the same memory
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
That's awesome! Appreciate the kind words!
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.
X. X
Just made a small mistake and I realized it after watching your video sir, Excellent explanation, thank you sir🙏
really nice, particularly how the minStack works here.
Thanks for pointing out hint. As soon as I saw hint, problem was solved in my head.
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.
the hint from leetcode was truly amazing tbh
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
Seriously the best
Great explanation!
Awesome clear video :)
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
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.
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?
Nice Explanation
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
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]
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].
@@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?
This is the solution I had as well. Was checking the comments to see if others arrived at the same solution. Nice.
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.
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]
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
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
this strategy is called 'augmented data structure'
Add this to stack playlist
MinStack Java Solution:
czcams.com/video/lHynQtJUcXs/video.html
Any other examples of your syntax from line 10?
This is so clever
thnak you sir
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)?
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]
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.
I'ts a perfect exercise to implement your own stack to :P
Please tell how to do it with O(1) space complexity.
Can you do accounts merge explanation please?
why can't we do return self.stack.pop() instead of return self.stack[-1]?
wow im over here thinking i had to make a stack class from scratch with a node class and everything lmao
Thanks
Leetcode updated this from an easy to medium level lol
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.
:)
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
Isn't the worst-case for both of these O(1)? Why would it take O(n)
@@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)
@@RM-xr8lq Thats right, I deleted my comment
@@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
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
So elegant
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?
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.
what data structure is the best if you want to implement your own stack instead using STL
whatever is the closest to a dynamic array.
Neat.
Neet*
You made it so easy!
Could you do Max Stack too?
It’s literally the reverse
I looked at this problem yesterday and it was listed as Medium.
This is marked as "easy" jeez, that O(1) Time complexity makes it medium at least
right!?!? It took me a minute to realize what I had to do for constant time.
it was changed to a medium
Took me more that a min. I used a array list instead of a stack for the minStack
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.
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
This is a Medium now
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)
Doesn't utilizing the min function on line 10 make the run time for that method O(n)?
no
This question is medium now 🧐
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😔😔👏👏
I don't really get the pop() function, doesn't it need a condition check before pop()ing out off the minStack ?
Nope, why? Every time you pop an element off the stack, you also pop the min at that level from the minStack.
@@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
@@Senzatie160 thnx lol
Done
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
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.
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]
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
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?
We can do this qn by O(N) space but it's super hard
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.
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)
getMin is O(n) in worst case, but the code from the video is O(1)
the thumbnail for this is a spoiler lol
If this is tricky, I am just wondering how tricky it is to do this without using any extra space??! I
store differences
probably have moved on but I just found a video with a pretty clever solution czcams.com/video/V09NfaGf2ao/video.html
Y pop from both stack
You have a bug in the pop method of your minstack class
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.
you actually do it by pushing differences, instead of actual values, for new minimums
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 ... 😶
i love u
斤斤計較
"Consider each node in the stack having a minimum value." How is a normal person supposed to understand this?
does python not have an inbuilt stack ? feel like you using an array for these stack problems kind of weird.
thats technically a list, but even so, for example the C++ vector can do push and pop
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.
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)
its o(n) time complexity for min function so doesnt work
i feel like this is a terrible interview question. You just need to know the trick and question solves itself
Pretty much all the coding interview rounds and their questions are like that (which is still a terrible thing)
isn't that all tech interview questions?
@@mikaylatheengineer9631 no some require mental application
@@CEOofTheHood only when you don’t know the tricks
@@motivewave001 what is the space complexity? is it 2n? can anyone tell
576. Out of Boundary Paths. Do a video on this