Design a MinStack LeetCode

One classic topic that is frequently asked in coding interviews is designing a Minimum Stack or MinStack. Let’s try to understand the problem and then its solution. The MinStack is a special type of stack that, in addition to the standard stack operations, also supports retrieving the minimum element in constant time making it a popular problem for testing one's understanding of data structures and algorithm optimization.

First, let’s understand what a stack is. A stack is a Last-In-First-Out (LIFO) data structure, meaning the element that was added last will be the first one to be removed. The basic operations on a stack are:

  1. Push: Add an element to the top of the stack.

  2. Pop: Remove the element from the top of the stack.

  3. Top: Return the element at the top of the stack without removing it.

Stack operations
Stack operations

Problem statement

The task is to create a stack data structure that supports the usual stack operations like push, pop, and top, while also efficiently returning the minimum element in constant time, i.e., O(1)O(1).

Constraints:

  • 231-2^{31} \leq val 2311\leq 2^{31}-1

  • All operations will always be called on a non-empty stack.

Examples

canvasAnimation-image
1 of 3

Knowledge test

Design a MinStack LeetCode

1

What will the getMin function return for the given stack?

stack = [1, -2, 3, 0]

A)

-2

B)

0

C)

1

D)

None of the above

Question 1 of 20 attempted

Algorithm

We will solve this problem by using the two-stacks approach, i.e., using an extra stack to keep track of the minimum element of a stack. This is one of the solutions which solves this problem efficiently by maintaining two stacks:

  • MainStack: This is the main stack where all the operations are performed.

  • AuxillaryStack: This is the extra stack that will contain the value of the minimum element of the main stack.

All stack operations are performed as per the usual process. The only new thing at each step would be to record the minimum value and store it in the auxiliary stack. We need to keep track of all the minimum values recorded for each step and we do this by storing them in the auxiliary stack. This way we will have a history of all the minimum values encountered so far. For example, if we push an element to the stack and it is smaller than the minimum value of the stack, then we will have to update the minimum value. Similarly, if we pop an item from the stack and it is the minimum value of the stack, again, we will update the minimum of the stack. Having a record of all the minimums will help us to quickly update the minimum value of the stack.

We will look into each operation of the stack and how MinStack is implemented:

  • Push(): When we push an element in the main stack, we check the auxiliary stack. If the auxiliary stack is empty, then we push this element in it as well. Secondly, if the element is smaller than the top of the auxiliary stack (minimum of the stack so far), we push the element to the auxiliary stack. Otherwise, we do not add this element in the auxiliary stack.

  • Pop(): For each element being popped from the main stack, we check if this is the top value of the auxiliary stack, meaning it is the minimum value of the stack. If it is, then we remove the top of the auxiliary stack as well.

  • Top(): This simply gives the top value of the main stack.

  • GetMin(): This is the top value of the auxiliary stack, which is the minimum value of the stack.

Let's look at an illustration to better understand the approach:

canvasAnimation-image
1 of 7

Coding example

Let's look at the implementation of the above-discussed approach:

class MinStack:
def __init__(self):
self.stack = []
# Initialize auxiliary stack to store minimum elements
self.aux_stack = []
# Implementation of push() method
def push(self, val):
# Add the value to the main stack
self.stack.append(val)
if not self.aux_stack or val <= self.aux_stack[-1]:
self.aux_stack.append(val)
# Implementation of pop() method
def pop(self):
if self.stack:
# Pop the top element from the main stack
val = self.stack.pop()
# If the popped element is the same as the top element of the minimum stack,
# also pop the top element from the minimum stack
if val == self.aux_stack[-1]:
self.aux_stack.pop()
# Implementation of top() method
def top(self):
if self.stack:
return self.stack[-1]
else:
return None
# Implementation of get_min() method
def get_min(self):
# Return the top element of the minimum stack if the minimum stack is not empty,
# otherwise return None
if self.aux_stack:
return self.aux_stack[-1]
else:
return None
def main():
min_stack = MinStack()
# Push some elements
min_stack.push(2)
min_stack.push(3)
# Display the current stack and minimum element
print("Main Stack:", min_stack.stack, "\tAuxiliary Stack:", min_stack.aux_stack)
print("\n\tMinimum Element:", min_stack.get_min())
print("-"*100)
print("After adding one more element")
# Push some elements
min_stack.push(1)
# Display the current stack and minimum element
print("\nMain Stack Now:", min_stack.stack, "\tAuxiliary Stack Now:", min_stack.aux_stack)
print("\n\tMinimum Element Now:", min_stack.get_min())
# Call the main function
if __name__ == "__main__":
main()
Design a Minstack LeetCode

As we have discussed the solution of the given problem, we will now discuss the complexity analysis of the solution.

Time complexity

The time complexity for all of the operations is O(1)O(1).

Space complexity

The space complexity is O(n)O(n) because we are using an auxiliary stack of size nn.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved