Mastering the MinStack: Efficiently Supporting Minimum Element Retrieval in Constant Time
Unlock the secrets of designing a stack that supports efficient minimum element retrieval with a step-by-step guide and Python implementation.
Table of contents
Introduction
Data structures are the backbone of efficient algorithms, providing the necessary foundation to solve complex problems swiftly and effectively. One intriguing challenge is designing a stack that supports not only the usual operations like push, pop, and top but also retrieving the minimum element in constant time.
This blog post delves into the MinStack problem from Leetcode, exploring the problem, key considerations, and a robust Python implementation.
Understanding the Problem
The MinStack problem requires creating a stack data structure that supports the following operations, all in constant O(1) time:
push(val)
: Pushes the elementval
onto the stack.pop()
: Removes the element on the top of the stack.top()
: Gets the top element of the stack.getMin()
: Retrieves the minimum element in the stack.
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 elementval
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
Key Considerations
Time Complexity
Ensuring all operations execute in constant time is paramount. This means each function (push
, pop
, top
, and getMin
) should have a time complexity of O(1)
.
Space Complexity
The solution must balance efficiency and space usage. Using additional data structures, like auxiliary stacks, can help achieve constant time complexity but may increase space complexity. Our approach uses two stacks: one to store all elements and another to store the minimum elements.
Edge Cases
Handling edge cases, such as operations on an empty stack or when multiple elements have the same minimum value, is crucial for a robust implementation.
Solution Strategy
To achieve constant time complexity for all operations, we use two stacks:
Main Stack (
stack
): Stores all the elements.Minimum Stack (
min_stack
): Stores the minimum elements at each stage.
Algorithm Design
Push Operation: When pushing a value, it's added to the main stack. If the minimum stack is empty or the new value is less than or equal to the current minimum, it's also pushed onto the minimum stack.
Pop Operation: The value is popped from the main stack. If this value is the current minimum (top of the minimum stack), it's also popped from the minimum stack.
Top Operation: Returns the top element of the main stack.
GetMin Operation: Returns the top element of the minimum stack, which is the current minimum.
Implementation in Python
Here’s the complete implementation of the MinStack class:
class MinStack:
def __init__(self):
# Initialize two stacks: one for all elements and one for minimum elements
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
# Push the value onto the main stack
self.stack.append(val)
# If the min_stack is empty or the new value is less than or equal to the current minimum, push it onto the min_stack
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
# If the main stack is not empty, pop the top value
if self.stack:
val = self.stack.pop()
# If the popped value is the current minimum, pop it from the min_stack as well
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
# Return the top value of the main stack if it is not empty
if self.stack:
return self.stack[-1]
return -1 # or raise an exception
def getMin(self) -> int:
# Return the top value of the min_stack if it is not empty (the current minimum)
if self.min_stack:
return self.min_stack[-1]
return -1 # or raise an exception
Important Considerations
Efficiency
The implementation ensures all operations—push
, pop
, top
, and getMin
—are executed in O(1) time complexity, making it highly efficient for stack operations.
Edge Case Handling
Empty Stack: The methods
top
andgetMin
handle cases where the stack is empty by returning a special value (-1
) or raising an exception.Duplicate Minimum Values: The
min_stack
correctly handles duplicate minimum values. When a minimum value is popped, only the corresponding entry in themin_stack
is removed.
Correctness
The use of two stacks ensures that the minimum value is always tracked accurately, maintaining the integrity of the stack operations.
Testing the Implementation
Testing is crucial to verify the correctness of the implementation. Here are some test cases to demonstrate the functionality:
def test_min_stack():
minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
assert minStack.getMin() == -3, "Test Case 1 Failed"
minStack.pop()
assert minStack.top() == 0, "Test Case 2 Failed"
assert minStack.getMin() == -2, "Test Case 3 Failed"
print("All test cases passed.")
test_min_stack()
Expected Outcomes
After pushing
-2
,0
, and-3
onto the stack,getMin
should return-3
.After popping the top element (
-3
),top
should return0
.After popping
-3
,getMin
should return-2
.
Conclusion
Designing a MinStack that supports constant time operations for pushing, popping, retrieving the top element, and finding the minimum element is a fascinating exercise in efficient algorithm design. By leveraging two stacks, we can achieve the desired performance, ensuring that all operations are handled in O(1)
time.
Implementing and testing this solution not only enhances understanding of stack data structures but also prepares one for tackling similar problems in coding interviews.
Related Articles
Some related LeetCode medium articles: