Interview Question: Max Stack

[@ianchui]

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

[@ByteByByte]

thank yoU!!

[@srivastava_prateek]

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

[@nayankurude6369]

Dont you think your 2nd stack approach is better, as you are using limited space. Here if u have a billion elements, then that much space is being wasted in this approach?

[@naraindaskeswani8623]

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

[@dev-skills]

MaxStack yet another data structure worth knowing :)

[@51aw0m1r]

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

[@alexsalevich2329]

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

[@hitec1691]

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

[@bbowles3]

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!

[@ByteByByte]

Yeah hadn't even thought of that. interesting point!

[@ramlongman5053]

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?

[@harshachandra0]

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.

[@coleenquadros4970]

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?

[@ByteByByte]

if we pop one that isn't the max then nothing changes because the max is still the same

[@aashishkalia8269]

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

[@ByteByByte]

Yep, you're right we need to fix how we update oldmax. Fixed it in the blog post

[@aashishkalia8269]

Thanks For helping Out.

[@aashishkalia8269]

The change You made in code is still incorrect try this:---> 1 97 1 120 1 25 2 3 According to your updated code it comes to be zero but in actual it is 120 got it?

[@parveensishodiya3527]

Aashish Kalia 😅 thanks for raising bro ..... BytebyByte will resolve it out

[@divyabharti9879]

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.

[@brycejohansen7114]

because the stack might contain duplicate values as you pop values off the stack, if you have two or more maximum values in the stack (One on top and the other somewhere else) then you need to be sure that you don't remove the maximum value until the rest of the same maximum values are removed.

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

[@ByteByByte]

If you pop 1 or 2, 3 is still the max. It's only if you pop 3 or push on something larger than 3 that the max changes

[@cheeseballoon]

Byte By Byte Ah thank you, I see it now.

[@abhishek7969]

Nice .. thanks from INDIA

[@sung3898]

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

[@TM-qc5oz]

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

[@pavanch9256]

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

[@saptarshimitra1267]

Cool video!

[@ByteByByte]

thanks!

[@Victor-xl4ru]

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

[@ByteByByte]

This exact problem? not likely, but it is a reasonable problem someone could ask

[@Victor-xl4ru]

thank you!

[@alexeystaroverov4804]

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

[@tourniquet3306]

If the stack is null you would get a NullPointerException. You don't need to explicitly throw it.

[@ByteByByte]

True. In this case I do like explicitly defining it, though, because it makes it much easier to read the code. You could also come up with some alternate way to handle that situation instead of a NPE

[@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" 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

[@pmrsuarus]

This implementation doesn't working because pop() always sets max to oldMax but push() doesn't always set oldMax push(2) // max points to 2 push(1) // max points to 2 but 1.oldMax is null pop() // max is set to 1.oldMax which is null max() // NullPointerExceptions public int pop() { if (stack == null) throw new NullPointerException; Node n = stack; stack = n.next; if (stack == null || n.oldMax != null) //

[@andrewcbuensalida]

There's already a throw new NullPointerException when stack == null in the beginning of the pop()

[@aronpop1447]

Stack is by definition LIFO.