Defne Eroğlu

Posted on

# Leetcode MinStack Design Problem: JavaScript Low Level Solution

With this post, I would like to share a low level Javascript solution for one of the most popular design problems from leetcode it is called MinStack.The problem expect a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Here instead of using Javascript's `length`, `Math.min()`, `push`, `pop` etc. , the expected functions are written at the low level as possible.

``````/**
* initialize data structure
*/
var MinStack = function () {

this.stack = [];
this.minVals = [];
this.count = 0;
this.min = Number.MAX_VALUE;
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {

if (x < this.min || this.count === 0) {
this.min = x;
}

this.minVals[this.count] = this.min;
this.stack[this.count] = x;
this.count++;

};

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

delete this.stack[this.count - 1];
delete this.minVals[this.count - 1];
this.min = this.minVals[this.count - 2];
this.count--;

};

/**
* @return {number}
*/
MinStack.prototype.top = function () {

return this.stack[this.count - 1]

};

/**
* @return {number}
*/
MinStack.prototype.getMin = function () {

if (this.count > 0)
return this.minVals[this.count - 1];

else if (this.count === 0)
return this.MinVals[0]
};

``````

#### MinStack:

• stack: is a storage of the values, in other words, the stack
• minVals: is a storage for the minimum Values; it is needed because after pop() operation we might delete the minimum value of the stack so the minimum values are also should be tracked.
• count: instead of using Javascript's `length` we can use `this.count` in order to set the last index and get the value of stack's last value.
• min: this is a kind of initial and global minimum value, that starts with the maximum numeric value in Javascript.

#### push(x):

Adds an element to the stack. Does not return any value.
Here, while adding new element(x) to the stack we also check that whether new element is less than the `this.min` value. Also include the case that, if the stack is empty, means `this.count===0`, then of course the first element of `this.minVals` is also equal to the new element(x). Both length of the stacks are equal which is the value of `count`.
Then instead of using Javascript's build in push() function, we say the last element of the stack is the new element:

``````...

if (x < this.min || this.count === 0) {
this.min = x;
}

this.minVals[this.count] = this.min;
this.stack[this.count] = x;
this.count++;
``````

#### pop():

Removes the last item from the stack. We are not going to use pop() function of Javascript. We just going to delete the last item from the stack. We need to consider that, maybe the value which is going to be removed is the minimum value of the array. So actually thats why we've needed an extra `minVals` stack instead of only with a `this.min`. In order to catch the new state of the stack, we need to also delete the last item of the `minVals` stack. But!
We also should remember that when we add new value to the stack with our `push(x)` function that is given above. There, we compare the x value with the `this.min` value, thats why `this.min` value is no longer the last item of the `this.minVals` stack but the previous one. And lastly, since we removed the last item from stack we should decrease the count number, so that when next time we do another operation, it should follow the last index of the stack with the count value.

``````...
delete this.stack[this.count - 1];
this.min = this.minVals[this.count - 2];
delete this.minVals[this.count - 1];
this.count--;
``````

#### top():

Returns the last item of the stack.
Here the length of the stack is equal to `this.count` and the last item of the stack is at the index of `this.count-1`:

`````` return this.stack[this.count - 1]
``````

#### getMin():

Returns the minium value of the stack. Here instead of scanning the whole stack, since we already set the minimum value to the `minStack` all the time. We can comfartably return the last item of minStack. Remember the last item's index is `this.count-1`; but if we are already at `count=0` then we simply should return the first value of the minStack:

``````...
if (this.count === 0)
return this.MinVals[0]
else
return this.minVals[this.count - 1];

``````

Alfredo Salzillo

Low-level javascript doesn't mean you cannot use the `class` sugar syntax and `const` or `let`.

And why you don't use the Array `length` like `count`?

``````class MinStack {
storage = [];
history = [];
min = Number.MAX_SAFE_INTEGER;
push(value) {
this.storage.push(value);
this.history.push({ min: this.min });
this.min = Math.min(this.min, value);
}
pop() {
const last = this.history.pop();
if (last) {
this.min = last.min;
}
return this.storage.pop();
}
top() {
return this.storage[this.storage.length - 1];
}
}
``````

The native `pop`and `push`should be better than the index assignment.

Defne Eroğlu • Edited

Thank you for your comments Alfredo. My point in this blog to share this particular solution I've submitted to leetcode. And I know, in the description of the problem, there is no rule that we cannot use `push()`, `pop()` or `length` functions and props ; but this was my solution. And I just wanted to share....
But your comment was very beneficial for me! Because I've gone more detail about these native functions, at least first just by google'ing the topic (as searching with the question that push() vs index assignment). Than I've found somethings I would like to share with you too.
The first search result I've found was from stackoverflow:
stackoverflow.com/questions/210346...
This post implies that push() is slower than array assignment. And I've found some similar discussions from old times they also say that push() is slower than array assignment. But they are very old post. I know node.js is much more better now and also the javascript engines of the browsers are increased in their performance. Than
I've made a test and my test environment is: Lenova, i7, node.js v12.18.3
Here is the test code:

``````var i = 0
var ar = []

i = 0
console.time("With index assignment")
while(i<=99999){
ar[i] = i
i++
}
console.timeEnd("With index assignment")

i = 0
ar = []
console.time("With push()")
while(i<=99999){
ar.push(i)
i++
}
console.timeEnd("With push()")
``````

And the result! push() is faster than index assignment! According to my tests you are right at the saying push(), pop() is faster than but; in the 2015 you were wrong I suppose... Anyways. As I've told at the beginning, I don't say this is the best and optimal solution, btw it was better the 75% of other commiters' submissions, my aim was to write these functions without Javascript's native related functions...And thank you again of course for your comment.

Rahul

Thank you for this. It seems a new post in Comments.

Amazing.