Where we last left off, we had a Stack
constructor with a push
, pop
and getMax
method on it. For my own sanity, I'm gonna rewrite the code so that we're using an array for our storage, and can just use native array methods.
function Stack(){
this.storage = [],
}
Stack.prototype.push = function(item){
return this.storage.push(item)
}
Stack.prototype.pop = function(){
return this.storage.pop()
}
Stack.prototype.getMax = function(){
return Math.max(this.storage)
}
So, Math.max()
has a time complexity of O(n). In the worst case, it has to iterate over all of the values we've got on our storage
in order to see what the highest value is. We can do a lot better than this.
In fact, we can reach the holy grail of time complexity, O(1).
I had to learn the solution from someone else, but I'll lay out some of my (failed) strategies before I tell y'all.
First, I figured that we could maintain a maximum value on our Stack
. It wouldn't be too hard, right? Just create a new property called max
or something like that, and update the value whenever we push
a higher value.
Given that all of the values we've got are passing through push
before they get to the storage
, we should be able to do some kind of work that will let us track what our max
is, right?
function Stack(){
this.storage = [],
this.max = -Infinity
}
Stack.prototype.push = function(item){
if (item > this.max) this.max = item;
return this.storage.push(item)
}
Stack.prototype.pop = function(){
return this.storage.pop()
}
Stack.prototype.getMax = function(){
return this.max
}
That works great! ...kinda.
Let's imagine we want to push
the numbers 3, 7, and 9 to our stack. We'll have a storage that looks like this: ['0': 7, '1':3, '2':9]
, and a max of 9
. Good so far, but let's pop
.
Now our storage looks like this: ['0': 7, '1':3,]
, but our max is still 9
! Not good!
So, we probably need something on our pop
that will update the max
value when we've popped our current highest
function Stack(){
this.storage = [],
this.max = -Infinity
}
Stack.prototype.push = function(item){
if (item > this.max) this.max = item;
return this.storage.push(item)
}
Stack.prototype.pop = function(){
const output = this.storage.pop();
if (output === this.max) this.max = Math.max(this.storage)
return this.storage.pop()
}
Stack.prototype.getMax = function(){
return this.max
}
This... is technically a solution in that getMax is an O(1) operation, but you know why that doesn't count, right?
Ultimately, we're still calling Math.max
in order to maintain our stack's max
value. We're just doing so in the definition of pop
. It's definitely less work than calling Math.max
every single time we need to get our max
, but it's still more than O(1) in our worst-case scenario.
So, let's reason about this a bit more. If our max
can't have its current value any more, what value should it have?
It should have its previous value. Okay, so how do we get that? The answer may surprise you.
function Stack(){
this.storage = [],
this.max = [-Infinity]
}
Stack.prototype.push = function(item){
if (item >= this.max) this.max.push(item);
return this.storage.push(item)
}
Stack.prototype.pop = function(){
const output = this.storage.pop();
if (output === this.max[this.max.length-1]) this.max.pop()
return this.storage.pop()
}
Stack.prototype.getMax = function(){
return this.max[this.max.length-1]
}
It feels so simple to look at now, but the way that we can maintain a 'history' for our max
is by creating a second stack. push
and pop
operate in O(1) time, so time complexity isn't an issue, especially because we're handling them inside of our stack push
and pop
methods.
So, let's walk through an example. If we push 3, 1, 7, 21, -5, 8
in sequence, our storage
will look like this: [3, 1, 7, 21, -5, 8]
, and our max
will look like this: [3, 7, 21]
.3
Now, let's pop
a value off our stack
.
If we pop
, our storage
will be [3, 1, 7, 21, -5]
. We popped 8
, and it's not the same as the last value in our max
stack, so the max
stack will be unchanged: [3,7,21]
.
Let's pop
a couple more values:
storage: [3, 1, 7, 21]
(popped -5), max: [3, 7, 21]
. 21
is the last item of our max
, which represents the highest value on our stack.
pop
again:
storage: [3, 1, 7]
(popped 21).
Here, we see that our 21
is the same as the last item of our stack, so we'll pop it off of our max
, and our max looks like this: max: [3, 7]
.
...And there you go!
It's utterly simple once you've got the trick, but it can be a challenge to shift the way that you conceptualize your max
value, especially since it uses the structure of a stack within your stack itself, but that's exactly what makes it cool!
Top comments (0)