# Create a min stack

Posted on

Problem

is taken from leetcode

Design a stack that supports push, pop, top, and retrieving the
minimum element in constant time.

push(x) — Push element x onto stack.

pop() — Removes the element on top of the stack.

top() — Get the top element.

getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); –> Returns -3.

minStack.pop();

minStack.top(); –> Returns 0.

minStack.getMin(); –> Returns -2.

My first solution

``````/**
* initialize your data structure here.
*/
var MinStack = function() {
this.repo = [];
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
if (!isNaN(x)) {
this.repo.push(x);
}
};

/**
* @return {void}
*/
MinStack.prototype.pop = function() {
return this.repo.pop();
};

/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.repo[this.repo.length - 1];
};

/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
if (this.repo) {
const copy = this.repo.slice(0);
return copy.sort((a,b) => a - b);
}
};
``````

My second solution

``````/**
* initialize your data structure here.
*/
var MinStack = function() {
this.repo = [];
this.minRepo = [];
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
if (!isNaN(x)) {
if (!this.minRepo.length || x <= this.minRepo) {
this.minRepo.unshift(x);
}
this.repo.push(x);
}
};

/**
* @return {void}
*/
MinStack.prototype.pop = function() {
if (this.repo.pop() === this.minRepo) {
this.minRepo.shift();
}
};

/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.repo[this.repo.length - 1];
};

/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
if (this.minRepo.length) {
return this.minRepo;
}
};
``````

For the second solution I was thinking of adding the numbers not from the back (with `push`) but instead from the front (with `unshift`). The advantage is that I would need less operation inside the method top (`return this.repo` would be sufficient – no need for calculating the last element with `this.repo.length - 1`). But I don’t whether this would be “weird” and would mean too much “mental mapping” (the function is called `push` but I use a `shift` inside).

Solution

### Inconsistent style

The `getMin` function checks if the stack is empty, and the `top` function doesn’t.
This inconsistency is confusing.
I’m not sure which way is better, but it’s good to be consistent.

### Unnecessary and over-eager input validation

`push` checks if the parameter is a number, and quietly does nothing if it isn’t.
If non-numbers should not be allowed, then it would be better to throw an exception than quietly ignore.
In any case, this check is not required by the exercise.

### Naming

Instead of `repo`, it would be more natural to call it `stack`.
With the `push` and `pop` methods of JavaScript arrays,
the illusion is perfect.

### Building from common building blocks

The second solution builds a secondary storage with the minimum values,
and makes some effort to avoid duplicates.
I’m not sure the extra effort is worth the added complexity.
It would be simpler to not try to avoid duplicates,
and simply add the pair of current and minimum values on every push.
Then, it becomes easy to see that an implementation is possible without reimplementing a stack: under the hood you can use a stack,
and the public methods simply encapsulate the transformations necessary for the underlying storage of value pairs.

``````var MinStack = function() {
this.stack = [];
};

MinStack.prototype.push = function(x) {
const min = this.stack.length ? Math.min(this.getMin(), x) : x;
this.stack.push([x, min]);
};

MinStack.prototype.pop = function() {
this.stack.pop();
};

MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
return this.stack[this.stack.length - 1];
};
``````

The `getMin` function is not constant. You need to keep track of the minimum value whenever you push or pop.

Furthermore you should name your functions.