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:
Push: Add an element to the top of the stack.
Pop: Remove the element from the top of the stack.
Top: Return the element at the top of the stack without removing it.
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.,
Constraints:
val
All operations will always be called on a non-empty stack.
Design a MinStack LeetCode
What will the getMin function return for the given stack?
stack = [1, -2, 3, 0]
-2
0
1
None of the above
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:
Let's look at the implementation of the above-discussed approach:
class MinStack:def __init__(self):self.stack = []# Initialize auxiliary stack to store minimum elementsself.aux_stack = []# Implementation of push() methoddef push(self, val):# Add the value to the main stackself.stack.append(val)if not self.aux_stack or val <= self.aux_stack[-1]:self.aux_stack.append(val)# Implementation of pop() methoddef pop(self):if self.stack:# Pop the top element from the main stackval = 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 stackif val == self.aux_stack[-1]:self.aux_stack.pop()# Implementation of top() methoddef top(self):if self.stack:return self.stack[-1]else:return None# Implementation of get_min() methoddef get_min(self):# Return the top element of the minimum stack if the minimum stack is not empty,# otherwise return Noneif self.aux_stack:return self.aux_stack[-1]else:return Nonedef main():min_stack = MinStack()# Push some elementsmin_stack.push(2)min_stack.push(3)# Display the current stack and minimum elementprint("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 elementsmin_stack.push(1)# Display the current stack and minimum elementprint("\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 functionif __name__ == "__main__":main()
As we have discussed the solution of the given problem, we will now discuss the complexity analysis of the solution.
The time complexity for all of the operations is
The space complexity is
Free Resources