Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)

Key Takeaways

weird flex but okay all right welcome back to the channel if you have not already subscribed to the channel subscribe to the channel my goal is to make this the premier resource the top resource for software engineering prep we've only done maybe 29 or 30 videos of like 250 videos that I want to get done so you're gonna need to know so many things for the interview and it's like all these subjects so that's why this is gonna take time to build up this library of videos so subscribe to stick with me I think in a year we're eventually going to complete this project anyway today we have a fascinating stack of question let's get straight into it right yeah alright so today we're gonna talk about the topic stack with dot max so whenever we say API I think of like web api's I used to think an API is like when we're interfacing with a web service or something so an API is called application programming interface all it is is a strict set of functions or properties behaviors we define from a certain system or a certain underneath set of logic that is going to provide us a certain behavior and this sets us the fundamental basis for what is called an abstract data type and ADT so a stack is an abstract data type so what does that mean it means we support an interface to the outside world we say hey I'm going to give you these behaviors I'm going to give you these properties you don't need to know how I do this it's you're interfacing with me I don't need to tell you how I'm doing it I'll do these things for you it's like we're signing it this is why they call it a contract and interfaces a contract we say I'm going to give you these services don't worry about how I do them just accept that I'll provide these to you in the way that I describe so it's like if you hire an electrician you don't worry about how he's fixing your lights you just worried that he's going to fix your lights you worry about the results the end behavior and not how it's done a stack it's an abstract data type we can implement it however we want but what it needs to support is two principal operations the push operation and the pop operation both of these operations operate in constant time no matter what the size of the stack is I know that what is going to happen is as input gets arbitrarily large or the size is arbitrarily large the time of pushing an item the time it takes to pop an item is not going to scale it's going to stay in a constant fashion it's going to stay constant so we need to support push and pop so that makes sense a stack is LIFO last in first out but this question says implement a max API that seems odd so now we need a max function we need a function that gives us the maximum item in a stack so that's that's an odd question to ask because a stack isn't really made for that and we would never even think this to appear on a stack but the whole point of this is to test how do you think test how you can work around these limitations that a stack gives us with this push and pop behavior now let's see the problem we run into and as always I want to walk you through the thought process the intuitions the the way that my brain goes solving this and then we'll slowly snake into the optimal solution now let's start with the problem that a stack provides us with this question whenever we are tackling these questions the key is figure out the problem before we even can figure out a solution so we need to see the barriers that our brain hits that we hit in this question that our structure limits us with before we even can solve it and continue with a solution I've given us a set of numbers that we're going to push and what we're gonna do is we're gonna just keep track of the maximum and what I want you to notice is the problem that we face so here's our strategy we're going to figure out how as we go along what I'm gonna do is I'm gonna push one so let's push one it does one be our maximum we initialize this with a negative infinity so does one be our maximum so we have nothing so one becomes the max okay that's cool so now let's push two so two gets pushed does to beat the maximum of course it does so now we put two as the maximum and push - all right great so now let's push three does three beat the maximum yes it does all right and now we push to there's to beat the maximum no it does not we push the two we did not change our max our max is still 3 so right now as it is if a caller was like hey I want the maximum from you stack we have no problem returning it in constant time we have it we know that now let's push the 0 to 0 B 3 no it doesn't just push it okay so our max is still 3 that makes sense and of course it is true we can see it is true so now push the 4 and we notice that our not changed for is the new maximum so everything is going right and we're doing fine constant time access bang we have the maximum our stack is behaving normally but the problem happens when we try to pop in Adam so let me pop the 4 so when we pop the 4 I realize for was my maximum so we need to adjust our maximum let's do that but wait this is a stack we we can't adjust our maximum because we don't know what the maximum is at this point in this state we don't know what the maximum was at this point we've lost it we over wrote the maximum because we overrode it we lose access when we pop this item so now we know our problem we have our problem so what is the solution to this problem did you just notice me saying state do you notice how we over wrote a state so the next mental leap I need you to make or that you would make in an interview solving this is you say hey I need to catch the maximum at each of these states at each of the pushes I'm going to see what was the maximum element as this item beat the maximum and I'm going to remember at every element what the maximum was so when I pop at this point the 0 needs to remember hey 3 was the maximum the 2 needs to remember 3 was the maximum 3 needs to remember well 3 itself is the maximum so 2 needs to remember that 2 is the maximum and one needs to remember that 1 is the maximum now let's do this new approach and again remember the problem is when we pop this we would have to do a linear time search then our max operation is not constant time our max must be constant time it cannot be linear in time we cannot search this in a linear fashion and it's a stack we would have to search it linearly we can't do any binary searches or anything because it's not sorted what we need to do is really the maximum hey I know the maximum I've cashed that state I already know it was so what we do is let's do our normal pushes so we push one we see we don't have a maximum one becomes a new maximum and one remembers that what is the maximum in the stack so forth okay cool so do you see this entry we have the normal one and then we see that one was the maximum so now we've completed that so now we push the two does oh I forgot to update the max by so now let's push the two does to beat the maximum yes to does beat the maximum and to is going to remember what the maximum was its itself it just beat the maximum so let's update our state okay so now that anything's going okay so if I pop this two then if I add this date I know that one is the maximum so let's continue so now let's push three does three beat the max yes and threes gonna remember the maximum which is itself alright so now we are at the two so let's push the two does two beats the maximum two does not beat the maximum three but what we do know is that we're going to catch this three we're going to know that the maximum when this item was pushed when the seven was pushed the maximum is three so we're gonna push the two and remember that and now let's push the zero again it does not be the maximum but we need to remember that our max below us is three so what we do is push the zero and now we see for four beats the maximum so we can push for and it's our new maximum it remembers itself as the max so for push so now I want you to see how this solves the problem that we're aiming to do you see how we're taking little jumps in our approach because we found our problem we gave it a little solution this is not the optimal solution in terms of space in terms of time yes but not in terms of space so we can pop this four so my caller says I want to top item give me the top item what's great is what's the max the max is three I know I remember I remember it and I did not lose it so I mean we won't even need this because we're going to remember this on the stack that was just for examples sake but we're going to remember this so what we do is we can pop again and again we're not lost anymore constant time access we remember it what is the max in the stack it's three what is the max in the stack it's two what is the max in the stack it is one this is a very good solution this is going to use linear space than linear time linear space is because for each of these nodes we're going to have to annotate with the maximum and that entails extra space so we know our worst case space is going to be all event but let me wonder can I improve the best case space when am I going to be able to opt to my space this is going to lead us into our optimal solution so what we do is as follows let me show you an example and then explain the intuition behind it okay so the optimal solution for this problem is going to be where we keep track of two stacks so this is going to be our item stack our actual value stack and this is going to be our maximum stack our cache of the maximum all right so now we have two stacks so wait why did I just make another stack so did you notice how when we did that we repeated three we cache the three we cache the three cache the three the problem is if I add an item like zero it will not be 30 it has no chance so the thing is we're going to be caching the same maximum on these nodes when they never had a chance to even beat the maximum so why not create a separate cache where I can say I've seen the maximum three three times if I pop a three I remove that maximum of three and then I've seen three two times so let's do a walk through this will not do you need to see this pictorially verbally it's not going to make sense so let's do this walk through very quickly all right so I have switched up the numbers so that we can actually see why this approves our space and why this is more optimal so what we're going to do is we're going to push - we don't have a maximal yet in our max cache so two is going to get an entry in the maximum cash and to is just going to be pushed to the actual stack so now we push to to the actual items and we've created a cache entry for this item in our max stack so we've seen the maximum - one time one occurrence of the maximum - so now we're gonna push another - and the reason this approach helps us is because we don't want to cache - as a maximum again we can just keep the occurrences over here so what we do is we're going to add the two and then we're going to increment this amounts because this is our DB maximum so this is going to become - and we're going to push that to okay so now this is the actual stack and this is the max stack so when we push the one we're going to peak the top of the max cache and we see that it does not be - so we're not even going to keep track of another - on this one we're about to push it will not even have a chance to be - beats the maximum so we just push the one and we don't even create an entry for it in the max cache do you notice how if a max operation was called we would have constant access to the maximum but the thing is this one contributes nothing to this so the one does not even influence this so so far we're fine so what we need to do now is push the for for is going to be a maximum because it beats this entry so we're going to create an entry for 4 and push it to the stack ok so we pushed for and now we again we know 4 is our maximum if we peek the max cache we're going to have our maximum item name costs in time so now we push a 5 we see 5 as a new maximum push it to the stack create a new cache entry okay we created a cache entry and together you see another 5 so all we do is we increment the amount of occurrences of the maximum 5 so now we see that this becomes 2 and we push another 5 and so now we push the 3 we see it doesn't beat the peak to maximum the maximum at the top so we just push 3 it contributes nothing and so now we're going to see what happens on pop so I know that this is the maximum 5 is the maximum so far so pop 3 is 3 in our max cache no it's not we do not need to adjust this just pop the 3 all right as 5 in our max cache is if the top entry yes it is deke remount to the - we only have one occurrence of 5 as a max and pop the five okay and now if we pop this five again we need to the commence a new one and we're going to do that now after we do that we notice that five does not have any more max entries so five gets popped off of the backs cache so now again if we were asked the maximum we have the answer for and that's correct so what we do now is we're going to pop four we are going to determine to the amount of occurrences of that in the max cache and that's what's going to happen so now we have zero occurrences of the four after doing that pop we noticed that so we pop this off of the backs cache and again constant time access to the maximum item it's - that's correct pop the one is the one going to be influencing this notes or knots because it doesn't even have an entry at the top so just pop the one so now we see a two and we know that's going to influence the max cache if it's popped this is going to take prevent and will pop and now finally we pop the tune we see it influences this this becomes zero this gets popped and after doing that popping we need to pop this item because there's no more occurrences so this is the approach that improves our best case space so as always I want to ask myself why why does this improve our best case space before was o of n every element would have to hold an item there we saw that it was roughly better but here is a case that really exemplifies why this approach is the best so let me push 5 and we see it's a new max entry and now let me push 0 we see that it does not influence the mass catch now let me push 0 now let me push 0 again it's not influencing our Max cash now let me push 0 and again let me push 0 and one more time let me push 0 do you notice that as our input can get arbitrarily large you give me 10 million zeroes the space is going to stay constant we're not going to scale the amount of space we use this is our best case if we get many items that do not influence this cache do you see why this approach is better instead of cashing a 5 on all of these zeros what we're going to do is that's it that's our maximum right there our best case for space can now be constant but we still bound in linear time because if we have to if the max changes frequently then we're going to have many entries on this max cache but this is this problem this is stack with the max API I don't even think we need to go over complexities because we know pushes constant time pop is constant time and Max is constant time and I've already discussed the space and how this improves our best keys so there's your complexities if you like this video like I like the video what I say if you like this video like the video oh my god I said it again if you like this video subscribe to the channel and like this video my goal is to make a great resource with clear explanations for these software engineering interview questions walking you through the thought process and how you can jump from what you know to what you don't know and seeing how you can work out of these difficult situations where you might not see the optimal solution going from problem to solution so that is my goal with this channel I want to create as much of an impact as possible and yeah that's what it's about [Music]