This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "MinStack Solution" Lesson
[00:00:00]
>> Bianca: So I'm moving on recursing back to our stacks and cues. So MinStack, super common interview question. This is a bit of a cool trick, because it's in constant time. Which we'll talk about tomorrow. But it's a pretty fast, it's a very, very fast way. To keep track of the minimum value in your stack, right?
[00:00:25] So if you think about ways you can find minimum value in your stack, is you can loop through all of your stacks. So you have to look at every single thing, every time you're looking for something, right? or every time you're either taking something off, putting something on you have to search, every little thing, each value, yeah?
[00:00:47] am I making sense? Cool, and that is not what we call constant time. We'll talk more about specifics tomorrow, but that is pretty slow if you think about a list that's like a bajillion things on us. That's a scientific term. All of you. Ask the math guy, right?
[00:01:03] bajillion
>> Male: Absolutely.
>> Bianca: Yeah. So you have a bajillion squares, and you're tryna. So as you're going through and you're adding, right, and you're like, this is the minimum. I'll keep comparing. It's not a big deal. But once you start taking off, then you're like, my gosh. What's the second minimum?
[00:01:21] And going, and going, and going, and then you have to search through, is that the second minimum, is that the second minimum. You have to check through all of them. Yeah? Cool. So this is a cool trick to avoid that. In the keys here, we have this second stack.
[00:01:39] We call it our MinStack, that lives inside of our other stack that we happen to call a MinStack. So as we're going through, it's kind of your standard, if we haven't reached capacity, and if the value is less, if the previous value is less than the current value that you're adding.
[00:02:07] If the previous value is less than the current value. Then you're gonna keep pushing every single time that minimum value. Otherwise, You're gonna push the new value because it's less than the last one. And this is your MinStack, by the way. This is a different stack from your storage here.
[00:02:32] And I’m gonna draw in a second, but I’m just gonna walk you through the code first. Yeah?
>> Female: So what's accumulating in the MinStack?
>> Bianca: The MinStack is gonna keep track of all of your minimum values. Any given sort of, You can think of it as different phases.
[00:02:53] As you add, add, and we'll be keeping track of the minimum all the time. As you pop, you'll keep popping and you'll always have the minimum. I'm gonna draw it in a second and it's gonna make more sense, I promise. I got a new toy. I'm ready to play.
[00:03:07] Let's see, if I can make it work. All right, so did that work? Here we go, all right. So, let's just say, let me stop for a moment. I'm gonna put this code here so we have something to reference.
>> Bianca: And I'll make it in pretty JavaScript for all of you.
[00:03:41] All right. So, this is imagine we have a stack called, myStack, and then we just are pushing some stuff on it, right? We're gonna push, push, push.
>> Bianca: Yeah, and then you can think, I'm gonna draw this as an array, but you guys know it's actually an object.
[00:04:04] So when we push the first one 1, 23, 9, 5 right? Makes sense? Great. So this is our actual stack. So as we're pushing, as you would expect you know our state changes. Our state is just like what does our data look like? So, at this point it looks like that, at this point, it looks like this, and at this point, it looks like, not like that, looks like this, 23 and 9, yeah?
[00:04:39] So we're growing our stack, easy. The difference between this one, this regular stack, this is our storage. And then we have our MinStack. So what our MinStack is doing, is every time we push something, we're gonna push a value into our MinStack. Every time. And it's always gonna be the minimum value at that state.
[00:05:08] So at this state it's gonna push this one.
>> Bianca: So I'm not gonna label all this, but we know that the first one is gonna be the storage and the second one is our minimum. So at this one, at this state, 1 is the minimum.
>> Bianca: I'm sorry, this is the second state, and 1 continues to be our minimum.
[00:05:32]
>> Bianca: Making sense? So now, if we did pop off from your stack,
>> Bianca: What this would look like, we're gonna pop it off, goodbye, goodbye. And we're still gonna keep track of that minimum there, okay? But I'm getting ahead of myself, let's go through the whole spiel.
>> Bianca: All right [NOISE] 1,1,1.
[00:06:16] This is a terrible example. I'm so sorry. So, it's gonna be-
>> Female: [LAUGH]
>> Bianca: Like this. So let's check out the code. So, what the code is saying here, so we're not at capacity. Whatever, we don't have the capacity, we don't care about that. So if the last one, if the value is greater then the last one, then you're gonna put the last one, I'm doing this wrong, guys.
[00:06:45] You're not calling me out. Then push the value, Okay. Here we go. I'm lying to you. Let's see. So if, the last one, no, no, no. Okay. No, no, I was right, I'm sorry. I am sorry. Let's do, let's not start with one, let's start with four. Nope, let's start with 6.
[00:07:18] This is a better example, don't you think? Are you guys following me? All right. Let's re-try here.
>> Bianca: Okay, here we are. Okay, so this is where it's a little bit different. Let's change our 1s to 6s. All right. So when we push the 5, we look, we peek at the last one.
[00:07:53] We say is this one less than the current one, and no it's not. So then we put a 5 there, cool? Awesome, and the reason is, is that every time we pop, we'll always have the last one on top. You won't have to search through our stack, and find it every time.
[00:08:16] So it's just an optimisation, it's kind of a
>> Bianca: You know, Min cycles are really common interview question, so just like keeping this in the back of your mind, super helpful. Well any question about this implementation?
>> Male: Question from the chart earlier. Tigan is asking why push the minimum value again?
[00:08:38]
>> Bianca: Why push the minimum value again? That's a great question. So the reason is that, the reason why we're pushing it multiple times is so that when you pop it, you're keeping track of which states but this is true. So,
>> Bianca: For the last state, which is this, right?
[00:08:59] It's true that 5 is the last one. But when we pop it off like this,
>> Bianca: In this state, which we can see here, it's true that 6 is the minimum, and that's true for all of the other ones. And the reason that we need to keep track of it, for each state is so that we don't have to go searching for it every single time.
[00:09:21] And that saves us time, makes it faster and we'll talk about specifics tomorrow, around that.
>> Bianca: So another question is, couldn't you just check to see if the top of the normal stack is equal, to the top of the min stack when you pop?
>> Bianca: So I think what they're saying is, if the one that you're popping off is the minimum one, the one that you're popping off is the same as the minimum.
[00:10:03] So that would somehow create a shortcut, like it does make it a little bit simpler to understand doing it that way, but when you need to find the next smallest one, you have to go and search for it. So you need to keep track of it for every state.
[00:10:17]
>> Male: In addition to that, if you had a duplicate number that was the minimum, you would've popped it off and you wouldn't know.
>> Bianca: Yeah, absolutely. For though we need to handle duplicates as well. Cool. All right. So that is a MinStack. Great. Should we do something with a queue now?
[00:10:41]
>> Male: Have we seen the pop? I'm sorry. Or is that on the git hub or.
>> Bianca: Yeah. All those solutions are in the solution branch. Yeah, so you can look at what pop looks like. The main difference, is you just pop off the Min. That's it.
>> Bianca: Great.
[00:11:07]
>> Bianca: All right. I forgot to draw a picture. Well. Did you guys get it without the picture? Okay.
>> Bianca: All right.
>> Female: Since so many people actually use a lot. Like I could see you doing MinStack and a Mc Stack and a mean stack or whatever.
>> Bianca: Yeah, yeah.
[00:11:26]
>> Female: Is it like a thing you actually use? [CROSSTALK]
>> Bianca: It's a useful thing, for sure. I've never used it, in real life or anything like that, but it is useful if you have a lot of data. It's really important, it would be really important to have something like this, so you don't have to search again?
[00:11:45]
>> Male: Yeah. And just as said generally something which is useful when they're doing the min max is not the actual value, but it's position in the stack.
>> Bianca: What do you mean by that?
>> Male: So you're not knowing exactly where that minimum is but you've got a certain number of layers to get to it possibly.
[00:12:04] So it says how much. How far am I from the minimum?
>> Bianca: mmmm, its so you would calculate that by the size of the stack before it changes value.
>> Male: right well you would use it the same way, it's just your positioning instead of the actual value.
>> Bianca: hm, mm ok ok
[00:12:24]
>> Male: better compared to like ascending or descending and then picking the value from the
>> Bianca: Like sorting it
>> Male: Yeah, sorting it and picking the
>> Bianca: It's much faster. But it takes more space. So there's a trade off. Like you have to store two stacks. But in terms of speed, it's faster.
[00:12:44] It depends on what your constraints are right? If you have a ton of space. But you need to do something quick. It might be useful yeah. Cool. If you have a stack and you don't care about the minimum or maximum number, probably very useless as well. Yeah. Cool.
[00:13:04] Yep question?
>> Male: Victoria's question. Would there be a difference in storing a single stack that has value, x min x, instead of two separate stacks?
>> Male: So, essentially, your stack frame is an object with two values.
>> Bianca: Yeah you could do that, you just don't normally wanna edit your data like that.
[00:13:30] If you are having some metadata about your data you usually don't wanna mutate your actual data. So, you could, it might be a bad idea, but yeah you could totally do that.