Leetcode - 155. Min Stack

#leetcode

Implementing MinStack in JavaScript

Problem Statement

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

Requirements:

push(val): Pushes the element val onto the stack.
pop(): Removes the element on top of the stack.
top(): Retrieves the top element.
getMin(): Retrieves the minimum element in O(1) time.

Optimized Approach (Using an Auxiliary Stack)

An auxiliary stack is an additional stack used alongside the main stack to store extra information that helps optimize certain operations.

In the case of MinStack, we use an auxiliary stack called minStack to keep track of the minimum element at each step. This allows us to retrieve the minimum value in O(1) time instead of scanning the entire stack.

To optimize getMin(), we use a minStack that stores the minimum element at each step, ensuring getMin() runs in O(1) time.

Code:

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

MinStack.prototype.push = function (val) {
    this.myStack.push(val);
    if (this.minStack.length === 0 || val <= this.getMin()) {
        this.minStack.push(val);
    }
};

MinStack.prototype.pop = function () {
    if (this.myStack.length === 0) return;
    let popped = this.myStack.pop();
    // If popped element is the current minimum, pop from minStack too
    if (popped === this.getMin()) {
        this.minStack.pop();
    }
};

MinStack.prototype.top = function () {
    return this.myStack[this.myStack.length - 1];
};

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

How It Works:

myStack[]: Stores all elements normally.
minStack[]: Stores the minimum element at each step.
When pushing:
- If val is smaller than or equal to the current min, we push it to minStack.
When popping:
- If the popped element was the min, we pop it from minStack too.

Time Complexity:

push(): O(1)
pop(): O(1)
top(): O(1)
getMin(): O(1)

Summary

Operation	Optimized Approach
push()	O(1)
pop()	O(1)
top()	O(1)
getMin()	O(1)

Using an auxiliary minStack significantly improves efficiency, making the getMin() operation O(1) instead of O(n). This is a crucial optimization for scenarios where retrieving the minimum element frequently is required.

DEV Community