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

0:00 - Read the problem
1:00 - Drawing Explanation
5:22 - Coding Explanation

leetcode 155

#amazon #stack #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[TechDevNick]

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

[josephjoestar]

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.

[ThePacemaker]

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

[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

[dollyvishwakarma]

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()

[sevenscapes]

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

[CST]

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.

[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!

[aldolunabueno]

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

[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

[KermitDominicano]

The hint made this so much easier. Instant realization lol

[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.

[devenlad]

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

[krishnaharshith]

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

[syafzal]

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

[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)

[shreyaschaudhary-rd]

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

[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

[deepak]

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.

[anonimettalontana]

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.