Is Min Stack easy or hard?

Min Stack is generally classified as a Medium problem. The individual operations are simple, but the challenge is designing the structure so getMin works in constant time without iterating through the stack.

How to solve Min Stack in O(1)?

Maintain the current minimum during each push operation instead of computing it later. With the two-stack approach, push the value to the main stack and update a min stack whenever the new value becomes the smallest. Alternatively, store pairs of (value, currentMin) in a single stack so the minimum is always accessible in constant time.

Min Stack Python or Java solution

In Python or Java, the typical implementation uses two stacks or a single stack storing pairs. Python often uses tuples like (value, min_so_far), while Java commonly uses a custom class or int array pair. Both approaches keep all operations in O(1) time.

What is the best approach for Min Stack?

The most common solution uses two stacks: one for normal stack values and another to track the minimum values. Every push updates the min stack when a new minimum appears, and getMin simply returns the top of the min stack. All operations run in O(1) time with O(n) additional space.

What data structure is used in Min Stack?

The primary data structure is a stack, typically implemented with an array or linked list. The optimized solution augments it with either a second stack to track minimum values or by storing (value, minimum) pairs in each stack node.

What is the time complexity of Min Stack?

A properly designed Min Stack supports push, pop, top, and getMin in O(1) time. This is achieved by maintaining extra state (such as a secondary min stack or storing the minimum with each element) so the minimum value never requires scanning the stack.

Is Min Stack asked at Google, Amazon, or Meta?

Min Stack is a common data structure design interview question and has appeared in interviews at companies like Amazon, Google, and Meta. It tests your understanding of stacks, constant-time operations, and how to augment a data structure with additional metadata.

Description Hints 1 Solution Video 8:53

155. Min Stack

Medium58.5% acceptance37 companies

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 1:

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:

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