- Published on
Design a Min Stack
- Authors
- Name
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.
Constraints
-2**31 <= val <= 2**31 - 1
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 3 * 10**4 calls will be made to push, pop, top, and getMin.
Examples:
- 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
Solutions
Approach 1 : using two stacks
You can design a stack that supports push, pop, top, and retrieving the minimum element in constant time using two stacks: one for the actual elements (let's call it the "main stack") and another for keeping track of the minimum elements (let's call it the "min stack")
class MinStack(object):
def __init__(self):
self.main_stack = [] # The main stack to store elements
self.min_stack = [] # The min stack to keep track of minimum elements
def push(self, val: int) -> None:
self.main_stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.main_stack:
if self.main_stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.main_stack.pop()
def top(self) -> int:
if self.main_stack:
return self.main_stack[-1]
else:
return None
def getMin(self) -> int:
if self.min_stack:
return self.min_stack[-1]
else:
return None
# Example usage:
# min_stack = MinStack()
# min_stack.push(3)
# min_stack.push(5)
# min_stack.push(2)
# min_stack.push(1)
# print("Top element:", min_stack.top()) # Output: 1
# print("Minimum element:", min_stack.getMin()) # Output: 1
# min_stack.pop()
# print("After popping, top element:", min_stack.top()) # Output: 2
# print("After popping, minimum element:", min_stack.getMin()) # Output: 2
Explanation
The design of this stack, which supports push, pop, top, and retrieving the minimum element in constant time, works because it uses an auxiliary stack (min_stack
) to keep track of the minimum element at any given time without the need for additional iterations or searching through the main stack. Let's break down why this approach works:
Main Stack (
main_stack
) for Storing Elements:- The
main_stack
is used to store all the elements that are pushed onto the stack. It behaves like a regular stack for maintaining the order of elements.
- The
Auxiliary Stack (
min_stack
) for Tracking Minimums:- The
min_stack
is used to keep track of the minimum element at any point in time. - When an element is pushed onto the
main_stack
, it's compared with the top element of themin_stack
. - If the element is less than or equal to the top element of the
min_stack
, it's pushed onto themin_stack
. This ensures that themin_stack
always contains the minimum element seen so far.
- The
Efficient Retrieval of Minimum Element:
- Since we are keeping track of the minimum element in the
min_stack
, retrieving the minimum element is a constant-time operation. We simply look at the top element of themin_stack
.
- Since we are keeping track of the minimum element in the
Consistent Popping of Elements:
- When an element is popped from the
main_stack
, we also check if it's the same as the top element of themin_stack
. If they match, we pop the top element from themin_stack
as well. This ensures that themin_stack
always correctly reflects the minimum element.
- When an element is popped from the
Here's why this approach works efficiently:
- Pushing an element onto the stack (both
main_stack
andmin_stack
) is a constant-time operation, O(1). - Popping an element from the stack (both
main_stack
andmin_stack
) is also a constant-time operation, O(1). - Retrieving the top element of the
main_stack
andmin_stack
is a constant-time operation, O(1).
By maintaining the min_stack
to track minimum elements as elements are pushed and popped from the main_stack
, this design allows you to efficiently keep track of the minimum element and perform all stack operations (push, pop, top) in constant time, meeting the requirements of the problem.