Create a min stack

Question

The task 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)[0];
 }
};

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[0]) {
 this.minRepo.unshift(x);
 }
 this.repo.push(x); 
 }
};
/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
 if (this.repo.pop() === this.minRepo[0]) {
 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[0];
 }
};

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[0] 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).

Answer 1

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()[0];
};
MinStack.prototype.top = function() {
 return this.stack[this.stack.length - 1][0];
};
MinStack.prototype.getMin = function() {
 return this.stack[this.stack.length - 1][1];
};

• thadeuszlay: Your solution requires more space, doesn't it?
• janos: @thadeuszlay it's on the same order of space complexity as yours (\$O(n)\$), but yes, on average it will use more space.

Answer 2

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.

• thadeuszlay: In the first solution you mean?
• thadeuszlay: In the second solution I keep track of the minimum value with every push and pop.
• konijn: Yes, I meant in the first anser.