Skip to main content
Talentd

Min Stack - Solution & Explanation

MediumStackDesign14 min readAsked at: Amazon, Microsoft, Apple +34
Practice this problem

Problem Statement

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:

  • -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.

Approach Overview

Problem Overview: Design a stack that supports the standard operations push, pop, and top, while also returning the minimum element with getMin() in constant time. The challenge is maintaining the minimum value without scanning the entire stack each time.

Approach 1: Two Stacks (O(1) time, O(n) space)

This approach keeps two stacks: the main stack storing all elements and a second stack tracking the current minimum. When you push a value, compare it with the current minimum. If it is smaller or equal, also push it onto the min stack. During pop, remove the value from the main stack and check whether it matches the top of the min stack; if so, pop from the min stack as well. The key insight is that the second stack stores only the values that become the new minimum at some point. This guarantees that getMin() simply returns the top of the min stack in O(1) time while keeping overall space at O(n).

Approach 2: Single Stack with Tuple Pairs (O(1) time, O(n) space)

Instead of maintaining two separate structures, each stack entry stores a pair: (value, currentMin). When pushing a new element, compute the minimum between the new value and the previous minimum stored at the top of the stack. Store that result alongside the value. Now every stack node already knows the minimum up to that point. On pop, simply remove the top pair. top() returns the value component, and getMin() returns the stored minimum component. This design keeps all operations in constant time and often results in cleaner implementations because the minimum state travels with each element.

Both solutions rely on the core idea that the minimum value must be updated incrementally during push operations rather than recomputed later. Without this trick, getMin() would require iterating through the entire stack, resulting in O(n) time.

This problem is a classic example of augmenting a data structure with additional metadata. Interviewers often use it to evaluate your understanding of stack behavior and your ability to extend a structure for constant-time queries. It also appears in discussions around system and data structure design, where tracking auxiliary state efficiently is common.

Recommended for interviews: The two-stack solution is the most widely expected answer because it clearly demonstrates the idea of maintaining a secondary structure for minimum tracking. The tuple-pair approach is equally optimal and sometimes preferred in languages where storing pairs or objects is straightforward. Showing the reasoning from naive O(n) minimum lookup to an O(1) design signals strong problem-solving ability.

Approach 1: Using two stacks

This approach utilizes two stacks. One stack will hold the main elements, while the other stack will keep track of the minimum elements. When you push a value, it's added to the main stack, and if it's less than or equal to the current minimum, it's also pushed onto the min stack. During a pop operation, if the value being popped is the current minimum, it's also popped from the min stack.

The C solution uses simple arrays to maintain the main stack and the minimum stack. We use indices to track the current position in both stacks. The main operations are very similar to basic stack operations but with an additional stack handling minimums.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.

Try this approach in the editor →

Approach 2: Using a single stack with tuple pairs

This approach reduces space usage by storing a pair (value, minimum so far) in a single stack. Each element maintains the current minimum alongside its actual value, providing quick minimum retrieval by just examining the top of the stack.

In C++, the standard stack is used, but each element is stored as a pair. The pair consists of the value and the minimum value at that time. This ensures that when popping, the integrity of the minimum remains intact because each element 'remembers' what the minimum was.

Code

C++JavaPython

C++

Java

Python

Complexity

Time Complexity: O(1) for each operation.
Space Complexity: O(n), each element only holds a pair so space is efficient relative to the number of elements.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using two stacks

Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.

Using a single stack with tuple pairs

Time Complexity: O(1) for each operation.
Space Complexity: O(n), each element only holds a pair so space is efficient relative to the number of elements.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two StacksO(1) for push, pop, top, getMinO(n)Most common interview solution. Easy to reason about and clearly separates value storage from minimum tracking.
Single Stack with Tuple PairsO(1) for all operationsO(n)Cleaner implementation when storing pairs is convenient. Keeps value and current minimum together in the same structure.

Video Solution

Design Min Stack - Amazon Interview Question - Leetcode 155 - Python • NeetCode • 349,169 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Min Stack with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Stack

Next

Sliding Window Maximum