Min Stack

StackDesign

EasyLeetCode #155

20 min

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 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.

You must implement a solution with O(1) time complexity for each function.

Example

Example 1:

Operation Sequence:

push(-2)min: -2

push(0)min: -2

push(-3)min: -3

getMin(-3)min: -3

pop()min: -2

top(0)min: -2

getMin(-2)min: -2

Solution

The challenge is to retrieve the minimum element in constant time. A standard stack doesn't support this. The solution is to use a second stack (or augment the primary stack) to keep track of the minimum value at each stage.

Algorithm Steps

Use two stacks: one for the actual values, and one to store the minimum value seen so far.
When pushing a value, push it to the main stack. For the min-stack, push the new value only if it's less than or equal to the current minimum.
When popping, if the popped value is the same as the top of the min-stack, pop from the min-stack as well.
The `getMin` operation simply returns the top of the min-stack.

Main Stack

Min Stack

Start with empty stacks.

Min Stack Solution


class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

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

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

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

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