155. Min Stack

Intuition

To achieve O(1) time complexity for both push, pop, top, and getMin operations, we can use an auxiliary stack to keep track of the minimum elements. By maintaining this auxiliary stack alongside the main stack, we can efficiently retrieve the minimum element whenever required without the need for scanning the entire stack.

Approach

1. Initialize Data Structures: - Use two lists (data and min_stack) where: - data stores all pushed elements. - min_stack keeps track of the minimum elements encountered so far.
2. Push Operation (push(val)): - Append val to the data stack. - If min_stack is empty or val is less than or equal to the top of min_stack, push val onto min_stack.
3. Pop Operation (pop()): - Pop the top element from data. - If the popped element equals the top of min_stack, also pop from min_stack.
4. Top Operation (top()): - Return the top element of data without removing it.
5. Get Minimum Operation (getMin()): - Return the top element of min_stack, which represents the current minimum element in the stack.

Complexity

Time Complexity:

• push(val), pop(), top(), and getMin() operations all run in O(1) time complexity because each operation directly accesses or manipulates the top elements of the stacks (data and min_stack).

Space Complexity:

• O(n), where n is the number of elements in the stack. The auxiliary min_stack can store additional elements equal to the number of elements in the main stack (data), resulting in linear space complexity relative to the number of operations performed.

Code

C++

class MinStack {
private:
    stack data_stack;
    stack min_stack;

public:
    MinStack() {
        
    }
    
    void push(int val) {
        data_stack.push(val);
        if (min_stack.empty() || val <= min_stack.top()) {
            min_stack.push(val);
        }
    }
    
    void pop() {
        if (!data_stack.empty()) {
            if (data_stack.top() == min_stack.top()) {
                min_stack.pop();
            }
            data_stack.pop();
        }
    }
    
    int top() {
        return data_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

Python

class MinStack:

    def __init__(self):
        self.data = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.data.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.data:
            popped = self.data.pop()
            if self.min_stack and popped == self.min_stack[-1]:
                self.min_stack.pop()

    def top(self) -> int:
        if self.data:
            return self.data[-1]
        return -1

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]
        return -1

Java

class MinStack {
    private Stack dataStack;
    private Stack minStack;
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        dataStack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        if (!dataStack.isEmpty()) {
            int removed = dataStack.pop();
            if (removed == minStack.peek()) {
                minStack.pop();
            }
        }
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

JavaScript

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

MinStack.prototype.push = function (val) {
    this.stack.push(val)
}

MinStack.prototype.pop = function (val) {
    this.stack.pop();
}

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

MinStack.prototype.getMin = function (val) {
    if (!this.stack.length) {
        return 0;
    }
    let min = this.stack[0];
    for (var i = 1; i < this.stack.length; i++) {
        min = Math.min(min, this.stack[i])
    }
    return min;
}