stack pt2: O(1) max

part 1 here

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 maxis 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!