Cracking the Code: Interesting LeetCode Min Stack Problem

Introduction

Hi, Guys. In this blog, I'll cover an interesting problem called Min Stack from a Leetcode. I believe that you people can get a deep understanding of stack data structure through this blog the implementation will be on Javascript, and I hope to inspire and empower you to make the most out of every moment.

Problem Statement

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 value) pushes the element value 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.

It would be best if you implemented a solution with O(1) time complexity for each function.

If you are not familiar with the Stack data structure, please read the below section. Otherwise, feel free to skip it.

---

Implementing Stack in JS

Stack

The stack data structure is a fundamental concept in computer science and is widely used in various applications. It follows the Last-In-First-Out (LIFO) principle, where the last element inserted is the first one to be removed.

For Example:
Imagine a stack of books, where you can only add or remove books from the top. This is similar to how a stack works in computer science. The top of the stack is called the "top" and the bottom is called the "base".

How to build a Stack?

Stacks are commonly implemented using arrays or linked lists. In this blog, we are going to use arrays for simplicity. In an array-based implementation, a fixed-size array is used on other strict types language but on javascript size of an array is calculated dynamically to store the elements of the stack.

The top of the stack is represented by an index pointing to the last inserted element. When a new element is added, the element is pushed, and when an element is removed, the top index is popped out.

Implementation

The implementation of the stack with push, pop, and top.

This is a simple implementation of a stack data structure. Now you can see the first 4 points of the problem are solved. The remaining getMin() method is pending. Let's find a solution to it.

---

Implementation of getMin() method

All other methods of a stack are on Big O(n). We can find the minimum of on a stack using a simple for loop of basic implementation. As bellow

// simple log(n) operation on stack to find the min
getMin() {

    let min = Number.NEGATIVE_INFINITY;

    for(let i=0;i<this.stack.length;i++) {

        if(this.stack[i] < min) {
            min = this.stack[i]
        }    
    }
    return min;
}

Even if we could sort the array after each push operation, it's a general solution and will cost too much. But, We need to find a solution with O(1) time complexity.

Solution

The idea behind the O(1) time complexity solution is to maintain one more stack which holds the minimum value of the stack at that point in time. Let illustrate the solution.

We can use two stacks to construct the special minimum stack. The first stack mainStackstores all the elements. The second stack, minStack, keeps track of the minimum numbers at a point in time.

The top of the mainStack contains the top element of the stack. Also, we can access the minimum element from the top of the minStack.

Example :

when we push the first number 5, we push it into both stacks

When we push the number 6, the top mainStack becomes 6. However, we don’t push it into minStack because it is greater than the current minimum 5

I hope you got a good idea about it. There is another way we can do it with one stack but a bit more complex to understand.

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

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

  if(!this.stack.length){
     this.minStack.push(val);
     this.stack.push(val);
     return;
  }

  this.stack.push(val); 

  let minStackIndex = this.minStack.length-1;

  if(val<this.minStack[minStackIndex])
      this.minStack.push(val);
   else 
      this.minStack.push(this.minStack[minStackIndex]);
};

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

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

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

Conclusion

In conclusion, the stack data structure is a fundamental concept in computer science that offers a simple and efficient way to manage data.

Share & comment your thoughts on it for more content like this.