Stack with Minimum

In process of the reading “Cracking the Coding Interview” I faced to very nice problem to solve:

Implement a Stack data structure extended with min() method which returns minimum value in the Stack. push(), pop() and min() should all operate in O(1) time.

The most obvious solution — to keep tracking the minimum value at each stage, so every node would have it’s own value + minimum value beneath of the stack. This solution is pretty simple and straightforward, but it’s obviously not the most effective.

We use too much memory for holding minimum values. Just image, we had added the smallest value at the very beginning of the stack, but we still hold it in each node! Let’s use a Stack instead! Ironic, isn’t it?

So, the most effective solution I know so far (and I think it’s the most effective solution ever) is using two Stacks: one for values itselves and another one for minimums.

In this case we just holding minimums in order they appeared. This allows to avoid useless duplication and reduce memory usage.

The ES6 code below implements described solution:

class StackWithMinimum {
constructor() {
this.valuesStack = [];
this.minimumsStack = [];
}

push(value) {
if (value <= this.min()) {
this.minimumsStack.push(value);
}
this.valuesStack.push(value);
}

pop() {
let value = this.valuesStack.pop();
if (value === this.min()) {
this.minimumsStack.pop();
}
return value;
}

min() {
let length = this.minimumsStack.length;
if (length) {
return this.minimumsStack[length - 1];
}
return Infinity;
}
}

https://github.com/davolokh/ctci/blob/StackWithMin/src/StackWithMin.js

Like what you read? Give Dmitry Volokh a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.