MediumStackDesign

Min Stack

1 approach, code in every language

Design a stack that supports pushing and popping elements while also being able to report the smallest element it currently holds, with every operation running in constant time.

Implement the MinStack class with the following methods: push(val) adds val to the top of the stack, pop() removes the element on top, top() returns the element on top without removing it, and getMin() returns the minimum element currently in the stack.

Every method must run in O(1) time. The methods top(), pop(), and getMin() will only be called when the stack is non-empty.

Example 1

Input: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output: [null,null,null,null,-3,null,0,-2]

After pushing -2, 0, -3, getMin() returns -3. Popping removes -3; top() then returns 0 and getMin() returns -2.

Example 2

Input: ["MinStack","push","push","getMin","pop","getMin"] [[],[5],[3],[],[],[]]

Output: [null,null,null,3,null,5]

With 5 and 3 on the stack, getMin() is 3. After popping 3, the minimum is back to 5.

Constraints

-2^31 <= val <= 2^31 - 1
Methods pop, top, and getMin are always called on a non-empty stack
At most 3 * 10^4 calls will be made to push, pop, top, and getMin

Auxiliary Minimum Stack

Keep a second stack that stores the running minimum at each level so getMin is a single read.

Loading animation…

Intuition

The challenge is that when you pop the current minimum you must instantly know the next smallest value without scanning. The trick is to remember, for every element, what the minimum was at the moment it was pushed. A second stack running in lockstep with the main stack solves this: each entry in the auxiliary stack is the minimum of everything at or below that level. When you push, you compare the new value with the current minimum and store the smaller of the two. Because both stacks grow and shrink together, popping the main stack also discards the stale minimum, and the new top of the auxiliary stack is automatically the correct minimum for the remaining elements.

Algorithm walkthrough

1Maintain a main stack for the values and an auxiliary stack for the running minimums.
2On push(val): push val onto the main stack; push min(val, current aux top) onto the aux stack, or val itself if the aux stack is empty.
3On pop(): remove the top of both stacks together so the two stay aligned.
4On top(): return the top of the main stack.
5On getMin(): return the top of the auxiliary stack, which is the minimum of all current elements.

Implementation

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.mins:
            self.mins.append(val)
        else:
            self.mins.append(min(val, self.mins[-1]))

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

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

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

Time

O(1)

Space

O(n)

Every operation touches only the tops of the two stacks. The auxiliary stack doubles the memory footprint.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free