#155

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Min Stack

Design a stack with O(1) operations to push, pop, retrieve the top element, and get the minimum element in constant time.

stack design

Problem Statement

You are tasked with designing a stack that supports four key operations: push, pop, top, and getMin. The twist is that all these operations must run in constant time, O(1). Implement a class, MinStack, that allows efficient access to the minimum element while maintaining stack integrity.

To achieve this, the solution must incorporate stack-based state management, where each node in the stack will track the minimum element at that point in time. Consider edge cases like maintaining correct values after pops and handling getMin calls during stack mutations.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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

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

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints

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

Solution Approach

MinStack Design

The solution can involve maintaining two stacks: one for the actual values and another for tracking the minimum value at each point. Each time a new element is pushed, compare it with the current minimum and store the new minimum in the second stack. This ensures that getMin can retrieve the minimum in constant time.

Push and Pop Operations

For each push operation, push the value onto the main stack and the minimum onto the auxiliary stack. For pop, remove elements from both stacks to maintain synchronization, ensuring that the minimum stack always has the correct value for getMin.

Top and getMin Operations

The top operation returns the value from the main stack. The getMin operation returns the top value from the auxiliary stack, which always stores the minimum value for the corresponding state of the main stack.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both time and space complexities are O(1) for all operations (push, pop, top, getMin). The auxiliary stack ensures that every operation can be performed in constant time. The space complexity depends on the size of the stack, but it remains linear in terms of the number of elements.

What Interviewers Usually Probe

Looking for efficient O(1) time complexity for all operations.
Check if the candidate handles the edge cases when the stack becomes empty.
Evaluate if the solution maintains stack synchronization properly, particularly with respect to the minimum tracking.

Common Pitfalls or Variants

Common pitfalls

Incorrect handling of stack underflow, especially for pop and getMin operations.
Failure to maintain the correct minimum values when elements are popped.
Confusion about how to manage two stacks or how to update the minimum value stack.

Follow-up variants

Implementing a stack that supports additional operations like peek.
Designing a thread-safe version of the MinStack for concurrent operations.
Optimizing space by reducing auxiliary stack usage while maintaining O(1) time complexity.

FAQ

What is the main challenge in solving the Min Stack problem?

The main challenge is ensuring that all operations—push, pop, top, and getMin—run in constant time, O(1), while maintaining correct tracking of the minimum value.

How can we efficiently track the minimum element in a stack?

You can use a secondary stack to track the minimum value. Every time a new value is pushed, compare it with the current minimum and store the smaller of the two in the secondary stack.

What is the time complexity of the Min Stack problem?

The time complexity for each operation (push, pop, top, getMin) is O(1), making the solution highly efficient.

Can the Min Stack problem be solved with just one stack?

While it's possible, using two stacks is the most straightforward and efficient approach to ensure constant-time operations for both min tracking and stack management.

How do you handle edge cases like empty stacks in the Min Stack problem?

Edge cases, such as popping from an empty stack or calling getMin on an empty stack, are managed by checking if the stack is empty before performing operations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class MinStack:
    def __init__(self):
        self.stk1 = []
        self.stk2 = [inf]

    def push(self, val: int) -> None:
        self.stk1.append(val)
        self.stk2.append(min(val, self.stk2[-1]))

    def pop(self) -> None:
        self.stk1.pop()
        self.stk2.pop()

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

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Continue Practicing

#173 binary search tree iterator #225 implement stack using queues #232 implement queue using stacks