stack pt2: O(1) max
Tags: algorithms, javascript, stack
Published: 2019-03-04 07:54:49

---
title: stack pt2: O(1) max
series: Implementing a Stack
published: true
description: 
tags: algorithm, javascript, stack
---

[part 1 here](https://dev.to/tttaaannnggg/implementing-a-stack-pt1-4djj)

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.

```javascript
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?

```javascript
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

```javascript
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.


```javascript
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!