Day 23 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#155. Min Stack(Easy/JavaScript)
Tags: javascript, webdev, programming, algorithms
Published: 2022-03-05 01:55:19

**Intro:** I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. **Here is my approach:**
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- **Combat the forgetting curve:** Re-do the question for the next three days. And come back regularly to revisit the problem.

******************************************

**155. Min Stack**
`Difficulty: Easy` `Language: JavaScript` 

<!--Goldman Sachs Interview-->

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

Implement the `MinStack` class:
- `MinStack()` initializes the stack object.
- `void push(int val)` pushes the element `val` onto the stack.
- `void pop()` removes the element on the top of the stack.
- `int top()` gets the top element of the stack.
- `int getMin()` retrieves the minimum element in the stack.

Example 1:
```
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2
```
Constraints:
- `-231 <= val <= 231 - 1`
- Methods `pop`, `top` and `getMin` operations will always be called on **non-empty** stacks.
- At most `3 * 104` calls will be made to `push`, `pop`, `top`, and `getMin`.

******************************************

**Solution:**
Highlight of this problem is constant time O(1) (note 2) is required instead of linear time. And the key to solve it is to **create two stack: one regular 'stack' and a 'min' stack to store minimun value of all elements being added**. To further explain, when a new element is added to the 'stack', compare this element with the smallest element in 'min' stack. If the new element is smaller than the smallest element in 'min' stack, add this new element to the 'min' stack. Otherwise, duplicate the smallest element in 'min' stack and push it to 'min' stack again. This way, the top element in the 'min' stack in always the minimum. And when we need to access the minimum value, we just need to get the top element in 'min' stack.
```
class MinStack {
    constructor() {
        this.stack = [];
        this.min = [];
    }

//construct (note 1) two stack under class MinStack. One regular
//'stack and the other 'min' stack used to store minimum value
    
    push(x) {
        if (!this.min.length) this.min.push(x);
        else this.min.push(Math.min(x, this.getMin()));

//If length (note 3) of 'min' stack does not exist (note 4), then
//it's an empty array. Push (note 5) element 'x' into 'min'
//stack.If 'min' stack is not empty, compare 'x' and the smallest
//value currently in 'min' stack, and push the smaller value into
//'min' stack. 

        this.stack.push(x);

//Push (note 5) element 'x' into the regular 'stack'.

    }
    
    pop() {
        this.min.pop()
        return this.stack.pop()

//Pop (note 6) last element from both stack

    }
    
    top() {
        return this.stack[this.stack.length-1];

//return last element of the stack

    }
    
    getMin() {
        return this.min[this.min.length-1];

//return last element of the stack which is also the minumum

    }
}
```
**Time and Space Complexity** 
- Time: O(1)
- Space: O(2N)

******************************************

**References:**
[LeetCode Problem Link](https://leetcode.com/problems/min-stack/)
[LeetCode Discussion: control_the_narrative](https://leetcode.com/problems/min-stack/discuss/740132/JavaScript-Clean-ES6-Class-Using-2-Arrays)
[Youtube: Andy Gala](https://www.youtube.com/watch?v=U62PyNFfBGE&t=426s)
[Note 1: Classes (JS/ES6)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes)
[Note 2: Constant time](https://en.wikipedia.org/wiki/Time_complexity#Constant_time)
[Note 3: Array.length](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/length)
[Note 4: Logical NOT (!)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Logical_NOT)
[Note 5: Array.push()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/push)
[Note 6: Array.pop()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/pop)
[Blog Cover Image Credit](https://www.istockphoto.com/portfolio/monsitj?mediatype=photography)