Min-Stack Optimized Solution Via JS

Min-Stack Optimized Solution Via JS#

Min-stack is a data structure that keeps track of the minimum element in a stack. It supports all the standard stack operations like push(), pop(), top(), and getMin(). However, the getMin() operation returns the minimum element in constant time O(1). In this PAA, we'll see how to implement a min-stack using JavaScript programming language.

Approach 1:#

We can implement a min-stack using two stacks. One stack will hold the actual elements, and the other stack will hold the minimum elements. Whenever we push an element into the stack, we compare it with the top element of the minimum stack. If the new element is smaller than the top element of the minimum stack, we push it into the minimum stack. Otherwise, we push the same top element again into the minimum stack. Similarly, while popping an element from the stack, we also pop an element from the minimum stack if it's equal to the popped element from the main stack. This way, we can keep track of the minimum element in constant time.

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }

  push(val) {
    this.stack.push(val);
    if (this.minStack.length === 0 || val <= this.minStack[this.minStack.length - 1]) {
      this.minStack.push(val);
    }
  }

  pop() {
    if (this.stack.pop() === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop();
    }
  }

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

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

Approach 2:#

We can also implement a min-stack using a single stack. In this approach, we store the difference between the current element and the minimum element so far beneath every element. This way, we can calculate the minimum element by subtracting the difference from the current element. While pushing an element into the stack, we also check if the new element is less than or equal to the current minimum element. If it's true, we push the difference between the current minimum and the new element into the stack.

class MinStack {
  constructor() {
    this.stack = [];
    this.min = Infinity;
  }

  push(val) {
    if (val <= this.min) {
      this.stack.push(this.min);
      this.min = val;
    }
    this.stack.push(val - this.min);
  }

  pop() {
    if (this.stack.pop() === this.min) {
      this.min = this.stack.pop();
    }
  }

  top() {
    const top = this.stack[this.stack.length - 1];
    return top < 0 ? this.min : this.min + top;
  }

  getMin() {
    return this.min;
  }
}

In conclusion, both approaches are equally valid and efficient in terms of time complexity. However, the first approach is more intuitive and easier to understand, while the second approach is more space-efficient as it uses a single stack instead of two. It's up to you to choose which one to use based on your requirements.