How do you solve Min Stack on LeetCode?

Min Stack (LeetCode #155) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(n) space complexity. Key insight: Using an auxiliary stack allows us to keep track of the minimum value efficiently.

What is the brute force solution for Min Stack?

The brute force approach for Min Stack is Brute Force, with O(n²) time complexity and O(n) space complexity. In this approach, we will use a simple stack to store all elements and find the minimum by scanning through the stack each time we need it. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Min Stack?

Min Stack uses the following concepts: Stack, Design. The recommended patterns to study are: Stack, Auxiliary Data Structures.

What are the interview tips for Min Stack?

Clearly explain your thought process and why you choose a specific approach. Consider edge cases, such as popping from an empty stack or retrieving the minimum from a single-element stack. Practice implementing the stack operations without looking at references to solidify your understanding.

What are common mistakes when solving Min Stack?

Not updating the min stack correctly during pop operations. Confusing the order of operations when accessing the top or minimum values.

#155

Min Stack

Medium

StackDesignStackAuxiliary Data Structures

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(n)	O(n)

💡

Intuition

Time O(1)Space O(n)

To achieve O(1) time complexity for getMin, we can use an auxiliary stack to keep track of the minimum values. Every time we push a new value, we also push the current minimum onto this auxiliary stack.

⚙️

Algorithm

4 steps

1Step 1: Create two stacks: one for the actual values and one for the minimum values.
2Step 2: When pushing a value, compare it with the current minimum and push the smaller one onto the min stack.
3Step 3: For pop, remove the top elements from both stacks.
4Step 4: For getMin, simply return the top of the min stack.

solution.py21 lines

1class MinStack:
2    def __init__(self):
3        self.stack = []
4        self.min_stack = []
5    
6    def push(self, val: int) -> None:
7        self.stack.append(val)
8        if not self.min_stack or val <= self.min_stack[-1]:
9            self.min_stack.append(val)
10    
11    def pop(self) -> None:
12        if self.stack:
13            val = self.stack.pop()
14            if val == self.min_stack[-1]:
15                self.min_stack.pop()
16    
17    def top(self) -> int:
18        return self.stack[-1] if self.stack else None
19    
20    def getMin(self) -> int:
21        return self.min_stack[-1] if self.min_stack else None

ℹ

Complexity note: All operations (push, pop, top, getMin) run in O(1) time because we only access the top of the stacks. The space complexity is O(n) due to the additional stack for minimum values.

1Using an auxiliary stack allows us to keep track of the minimum value efficiently.
2Both stacks maintain a relationship where the min stack always has the current minimum at the top.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.