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!

Posted on by:

### tang

"Poets do not go mad; but chess-players do. Mathematicians go mad, and cashiers; but creative artists very seldom." -GK Chesterton

## Discussion