# Check for max value in stack

Posted on

Problem

Got this problem in a coding interview –
Get the max value of a stack in O(1).
The stack contains numbers only.
Please review my solution.

``````class Stack {

data;
maxVal;

pop() {
return this.data.pop();
}

insert(x) {
const cm = new CheckMax();
this.data.push(x);
this.maxVal = cm.max.call(this);
}

peek() {
return this.data[this.data.length - 1];
}
}

class CheckMax {

max() {
let maxVal = this.maxVal;
let oldVal;
if (this.data.length > 0) {
oldVal = this.peek();
if (maxVal == undefined) {
maxVal = oldVal;
}
if (oldVal > maxVal) {
maxVal = oldVal;
}
}
return maxVal;
}
}

const stack = new Stack();
stack.data = [];
stack.insert(123);
stack.insert(22);
stack.insert(23);
stack.insert(9);
stack.insert(73);
stack.insert(54);
console.log(stack.maxVal);``````

Solution

This solution looks incorrect and doesn’t cover the case when the max value is popped.

For example,

``````const stack = new Stack();
stack.data = [];
stack.insert(1);
stack.pop();
console.log(stack.maxVal); // even though stack is empty, this will print 1, right?
``````

I think one naive way to solve this is to store (internally) the max value along with the element value, at time of element insertion.

``````class Entry {
constructor(value, maxValue) {
this.value = value;
this.maxValue = maxValue;
}
}
// insert 1
[new Entry(1, 1)]
// insert 2
[new Entry(1, 1), new Entry(2, 2)]
// insert 1 - notice how the latest Entry has a value property of 1 but a maxValue property of 2 since the largest property seen so far is 2
[new Entry(1, 1), new Entry(2, 2), new Entry(1, 2)]
// pop - look at last Entry's max value to see max value (2)
[new Entry(1, 1), new Entry(2, 2)]
// pop - look at last Entry's max value to see max value (1)
[new Entry(1, 1)]
// pop - empty, so max value is undefined / null
[]
``````

One way to implement this would be something like this

``````class Stack {
constructor() {
this.entries = [];
}

get maxValue() {
// this value can be stored in an instance variable and updated on pop/push if access to value will occur frequently
if (0 < this.entries.length) {
return this.entries[this.entries.length - 1].maxValue;
}
return null;
}

pop() {
return this.entries.pop();
}

push(value) {
this.entries.push(
new Entry(
value,
Math.max(
value,
this.maxValue
)
)
);
}
}
``````

Another thing to watch out for – in every call to `insert` you are instantiating a new `CheckMax` instance which seems wasteful. `CheckMax` doesn’t really contain any state and the `this` is referring to an instance of a `Stack`. I think it’s more natural to add the logic in `CheckMax` on `Stack` itself.

Finally, the setting of the `data` property on a `Stack` instance seems like an internal implementation detail that the caller should not be worried about. I don’t think the caller should have to initialize the `data` property on a `Stack` instance in order for it to work correctly. Whatever data structure the stack uses under the hood to keep track of elements should not be the concern of the caller of the stack.

The answer by Jae Bradley already mentions great points – the code should handle the case where elements are removed, and it is strange that the method in the `CheckMax` class is separate from the `Stack` class.

## Formatting

If I saw this code in an interview one of the first things I would look at is the formatting – e.g. indentation, spacing. The indentation looks fairly consistent – i.e. two spaces, though the properties `data` and `maxVal` are indented with six spaces.

## uninitialized `data` property

It seems strange that the `data` field is not initialized to an array when declared, and the sample usage assigns it before calling the `insert` method. If the class was used and the `data` property wasn’t assigned then the following error would occur:

VM35:12 Uncaught TypeError: Cannot read property ‘push’ of undefined

## comparison operators

In the `CheckMax::max()` method there is a loose comparison operator used:

`````` if (maxVal == undefined) {
``````

A good habit and recommendation of many style guides is to use strict equality operators (i.e. `===`, `!==`) whenever possible (like is used in the snippet above). The problem with loose comparisons is that it has so many weird rules one would need to memorize in order to be confident in its proper usage.