Interview Question: Max Stack

In this video, I show how to create a stack that with push(), pop(), and max() functions.

Do you have a big interview coming up with Google or Facebook? Do you want to ace your coding interviews once and for all? If so, Byte by Byte has everything that you need to go to get your dream job. We've helped thousands of students improve their interviewing and we can help you too.

You can also find me on

[ianchui]

Dude, the quality of these videos are in SANE.
good job dude!

[srivastava_prateek]

Awesome approach till now i used 2nd stack to keep hold of max operation.

[dev-skills]

MaxStack yet another data structure worth knowing :)

[naraindaskeswani]

Instead of storing pointer to oldMax, can we just store the value in oldMax and not the reference to node containing oldMax ?

[slawekmazur]

there's one missing bit here. in `pop()` when `null == stack` -> `max = null`

[alexsalevich]

the best way is just save the max for every push, meaning we just keep a max stack that you push there the max up to the latest push/pop

[bbowles]

Whats kind of interesting about this problem is that it wouldn't work with a Queue because the you could derive a test case where the oldmax value was no longer correct. In the case of a Queue, I think you'd need to also maintain a heap of items. Would be another fun problem!

[hitec]

Superb video :). Could please use dark theme editor as this white background is quite hard on the eyes. Thanks

[ramlongman]

What if you pop and there's only 1 element in the stack? You're not changing the max value in this case. Will it still be the value that you popped? Shouldn't you set max to null in this case?

[harshachandra]

Is there any difference between Approach1 and Approach2 in terms of appropriateness of memory handling?
In both the approaches I have removed throwing null pointer exception part of the code.

Approach1 (Sam's approach):

int pop() {
Node n=stack;
stack=n.next;
if(n.oldMax!=null) max=n.oldMax;
return n.value;
}

Above approach is able to signal that Node n is going out of scope hence we have a way to signal that destructor has to be called. I am thinking C++ way here.

Approach2 (My approach):

int pop() {
int value = stack.value;
if(stack.oldMax!=null) max=stack.oldMax;
stack=stack.next;
return value;
}

Above approach completely relies on the intelligence of garbage colelctor to decide that the earlier "stack" node is dangling now and has to be collected and free'd.

[TM-qcoz]

the "x1 ..x2...x3..x4" expression was funny. :)

[pavanch]

In pop method if condition add this condition
if(stack==null || n.oldMax!=null)

[coleenquadros]

Hi, for the pop part. you have taken care of the case if the element that is popped is the max value and so we assign max to the next. what if the element popped is not the max value in the stack? Shouldn't you check for the case if the element that is popped is actually the max value in stack?

[cheeseballoon]

Great solution, but I think there's a very likely case that isn't handled by this implementation. If I push 3, 2, then 1, stack will be 1->2->3->null, and max will be 3->null. Once you pop once, there are still elements in the stack, but there's no longer a max. The problem is that any time an element is pushed that's not the max, but also not the min, it won't be registered as a candidate for max later. I don't think this bug can be solved while maintaining constant time.

[sung]

shouldn't your value, next, oldMax be public and not private?

[aashishkalia]

hey i have a doubt run this test case
1.push
2.pop
3.max
test case:-
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

your code gives wrong output for maximum always gives 97 even though it is not present
bcz you have not handled the case if oldmax is null for the node . got it?


Or simply try this :
1 97
2
3

what is maximum according to Your code is 97 .But it should be zero since 97 is popped out.
As you havenot updated max for the case if oldmax=null

[divyabharti]

Hey Sam, one question How come link list node are pointing to old max .as soon as we change the max value the node will start pointing to new max. As same copy of max will be modified in memory.

[alexeystaroverov]

+to u at least because u're using a mic! ( unlike half of video which a dying due to poor sound )))

[pursuitofcat]

We can record max_yet on the node of all of the nodes encountered yet. Like so:


class Node:
def __init__(self, val=None):
self.val = val
self.next = None
# holds the maximum val encountered yet!
self.max_yet = None

def __str__(self):
return f"Node<{self.val} [{self.max_yet}]>"


class Stack:
def __init__(self):
self.head = None

def push(self, val) -> None:
if self.head is None:
self.head = Node(val)
self.head.max_yet = val
else:
old_head = self.head
self.head = Node(val)
self.head.next = old_head
self.head.max_yet = max(old_head.max_yet, val)

def pop(self) -> Node:
if self.head is None:
raise KeyError("Nothing to pop")
old_head = self.head
self.head = self.head.next
return old_head

def max(self) -> int:
if self.head is None:
raise KeyError("No items in the stack")
return self.head.max_yet


s = Stack()
s.push(1)
s.push(2)
s.push(3)
assert s.max() == 3
s.push(2)
assert s.max() == 3
s.push(1)
assert s.max() == 3
s.pop()
assert s.max() == 3
s.pop()
assert s.max() == 3
s.pop()
assert s.max() == 2
s.push(5)
s.push(4)
assert s.max() == 5
assert s.head.next.max_yet == 5

[Victor-xlru]

what are the chances of this being asked in an interview?