How do you approach Min Stack?

Use an auxiliary stack to track the minimum at each level.

What is the key insight for solving Min Stack?

Solution: Two Stacks Maintain a main stack and a min stack. The min stack tracks the minimum value at each level. When pushing, push to the min stack if the value is less than or equal to the current minimum. Time Complexity: O(1) for all operations Space Complexity: O(n)

← Back to problems

Min Stack

MediumData Structures

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the `MinStack` class: - `push(val)` pushes the element val onto the stack. - `pop()` removes the element on the top of the stack. - `top()` gets the top element of the stack. - `getMin()` retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function. **Note:** For this problem, implement operations as a function that takes a list of commands and returns the results. Return `null` for void operations (push, pop).

Example 1

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

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

Explanation: push(-2), push(0), push(-3), getMin() returns -3, pop() removes -3, top() returns 0, getMin() returns -2.

Constraints

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

Loading editor...