155. Min Stack
Problem Description
The problem requires designing a stack data structure with not only the standard operations - push
, pop
, and top
- but also the ability to retrieve the minimum element present in the stack at any time, all in constant time O(1). This is quite challenging because the standard stack data structure does not keep track of the minimum element, and searching for the minimum element typically requires O(n) time where n is the number of elements in the stack.
To summarize, MinStack
class should support these operations:
MinStack()
constructor that initializes the stack.push(int val)
that adds an element to the stack.pop()
that removes the element at the top of the stack.top()
that retrieves the element at the top of the stack without removing it.getMin()
that retrieves the minimum element present in the stack.
Each of these operations must be done in O(1) time complexity.
Intuition
To maintain the minimum element information in constant time, we need a strategy that keeps track of the minimum at each state of the stack. The solution uses two stacks:
- The first stack
stk1
behaves like a normal stack, holding all the elements. - The second stack
stk2
keeps track of minimum elements. Each element instk2
corresponds to the minimum element ofstk1
up to that point.
With each push
, we insert the value into stk1
and also update the stk2
with the minimum of the new value and the current minimum, which is the top element of stk2
.
Upon pop
, we simply remove the top elements from both stk1
and stk2
. Given stk2
is always in sync with stk1
but only storing minimums, it ensures that stk2
's top always represents the current minimum of stk1
.
top
is straightforward as we return the top element of stk1
whereas getMin
returns the top element of stk2
.
This design allows for the stack to operate as normal while having a supporting structure, stk2
, that efficiently tracks the minimum element. Thus, all the required operations run in constant time, fulfilling the problem constraints.
Learn more about Stack patterns.
Solution Approach
The solution involves using two stacks to keep track of the minimum element in conjunction with the main stack operations. Here is how the solution is implemented for each function of the MinStack
class:
__init__(self)
- Initialize two empty lists,
self.stk1
andself.stk2
. The first listself.stk1
is used as the primary stack to store the values. The second listself.stk2
serves as an auxiliary stack to store the minimum values seen so far. - Append
inf
(infinity) toself.stk2
to handle the edge case when the first element is pushed onto the stack.
push(self, val: int)
- Append the value
val
to the primary stackself.stk1
. - To maintain the minimum in
self.stk2
, append the minimum of the new valueval
and the last element inself.stk2
(which is the current minimum) toself.stk2
.
pop(self)
- Pop the top element from
self.stk1
, which is the standard stack operation. - Similarly, pop the top element from
self.stk2
. This ensures that after the pop operation, the minimum value is updated correspondingly inself.stk2
.
top(self)
- Return the top element of
self.stk1
by accessing the last element in the listself.stk1[-1]
without removing it. This is the standard 'peek' operation in stack.
getMin(self)
- Return the top element of
self.stk2
by accessing the last element in the listself.stk2[-1]
. Sinceself.stk2
is maintained in a way that its top always contains the minimum element of the stack, this gives us the current minimum in constant time.
In conclusion, the algorithm leverages an auxiliary stack self.stk2
that mirrors the push and pop operations of the primary stack self.stk1
. It cleverly keeps track of the minimum element at each level of the stack as elements are added and removed, which allows for constant time retrieval of the minimum element. This elegant solution satisfies the constraints of the problem statement and ensures that all operations - push
, pop
, top
, and getMin
— remain constant time O(1)
operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
-
Construct a
MinStack
. Initially, bothstk1
andstk2
are empty:1stk1: [] 2stk2: [inf]
inf
instk2
is used as a placeholder to simplify the push operation even when the stack is empty. -
Push the value
5
onto the stack.1push(5)
stk1
now holds:[5]
stk2
updates its minimum value by comparing the current minimum (inf
) and5
, choosing the smaller one:[inf, 5]
-
Push the value
3
onto the stack.1push(3)
stk1
now holds:[5, 3]
stk2
updates:[inf, 5, 3]
as3
is the new minimum. -
Push the value
7
onto the stack.1push(7)
stk1
now holds:[5, 3, 7]
stk2
updates by comparing3
(current minimum instk2
) and7
, which results in:[inf, 5, 3, 3]
(since3
is smaller). -
Retrieve the current minimum.
1getMin()
The top of
stk2
gives us the minimum:3
. -
Pop the top element off the stack.
1pop()
After popping,
stk1
holds:[5, 3]
Andstk2
synchronously pops as well to maintain the minimum:[inf, 5, 3]
. -
Retrieve the new current minimum.
1getMin()
With the last
7
removed, the new top ofstk2
and thus the current minimum is now:3
. -
Retrieve the top element.
1top()
The top of
stk1
gives us the last pushed value which is not removed yet:3
.
By following the above steps for each operation, it is demonstrated that the auxiliary stack stk2
accurately keeps track of the minimum elements for the primary stack stk1
at each point of operation, ensuring that getMin()
can always retrieve the current minimum in constant time, O(1)
.
Solution Implementation
1class MinStack:
2 def __init__(self):
3 # Initialize two stacks; one to hold the actual stack values,
4 # and the other to keep track of the minimum value at any given point.
5 self.stack = []
6 self.min_stack = [float('inf')] # Initialize with infinity to handle edge case for the first element pushed
7
8 def push(self, val: int) -> None:
9 # Add the value to the main stack
10 self.stack.append(val)
11 # Add the minimum value to the min_stack which is the minimum of the new value and the current minimum
12 self.min_stack.append(min(val, self.min_stack[-1]))
13
14 def pop(self) -> None:
15 # Remove the top value from both main stack and min_stack
16 self.stack.pop()
17 self.min_stack.pop()
18
19 def top(self) -> int:
20 # Return the top value of the main stack
21 return self.stack[-1]
22
23 def get_min(self) -> int:
24 # Return the current minimum value which is the top value of the min_stack
25 return self.min_stack[-1]
26
27# Example of how the MinStack class can be used:
28# min_stack = MinStack()
29# min_stack.push(-2)
30# min_stack.push(0)
31# min_stack.push(-3)
32# print(min_stack.get_min()) # returns -3
33# min_stack.pop()
34# print(min_stack.top()) # returns 0
35# print(min_stack.get_min()) # returns -2
36
1class MinStack {
2 // stk1 keeps track of all the elements in the stack.
3 private Deque<Integer> stack = new ArrayDeque<>();
4
5 // minValuesStack keeps track of the minimum values at each state of the stack.
6 private Deque<Integer> minValuesStack = new ArrayDeque<>();
7
8 // Constructor initializes the minValuesStack with the maximum value an integer can hold.
9 public MinStack() {
10 minValuesStack.push(Integer.MAX_VALUE);
11 }
12
13 // Method to push an element onto the stack. Updates the minimum value as well.
14 public void push(int val) {
15 // Push the value onto the stack.
16 stack.push(val);
17 // Push the smaller between the current value and the current minimum onto the minValuesStack.
18 minValuesStack.push(Math.min(val, minValuesStack.peek()));
19 }
20
21 // Method to remove the top element from the stack. Also updates the minimum value.
22 public void pop() {
23 // Remove the top element of the stack.
24 stack.pop();
25 // Remove the top element of the minValuesStack, which corresponds to the minimum at that state.
26 minValuesStack.pop();
27 }
28
29 // Method to retrieve the top element of the stack without removing it.
30 public int top() {
31 // Peek the top element of the stack.
32 return stack.peek();
33 }
34
35 // Method to get the current minimum value in the stack.
36 public int getMin() {
37 // Peek the top element of the minValuesStack, which is the current minimum.
38 return minValuesStack.peek();
39 }
40}
41
1#include <stack>
2#include <climits> // needed for INT_MAX
3using namespace std;
4
5class MinStack {
6public:
7 // Constructor initializes the auxiliary stack with the maximum integer value.
8 MinStack() {
9 minValuesStack.push(INT_MAX);
10 }
11
12 // Pushes a value onto the stack and updates the minimum value stack.
13 void push(int val) {
14 mainStack.push(val);
15 // Push the current minimum value onto the auxiliary stack.
16 // Compares the new value with the current top of the minValuesStack.
17 minValuesStack.push(std::min(val, minValuesStack.top()));
18 }
19
20 // Pops the top element from both the main stack and the minimum value stack.
21 void pop() {
22 mainStack.pop();
23 minValuesStack.pop();
24 }
25
26 // Retrieves the top element of the main stack.
27 int top() {
28 return mainStack.top();
29 }
30
31 // Retrieves the current minimum value from the auxiliary stack.
32 int getMin() {
33 return minValuesStack.top();
34 }
35
36private:
37 // Main stack to store the elements.
38 stack<int> mainStack;
39 // Auxiliary stack to store the minimum values.
40 stack<int> minValuesStack;
41};
42
43/**
44 * The following comments illustrate how a MinStack object is used:
45 * MinStack* obj = new MinStack();
46 * obj->push(val);
47 * obj->pop();
48 * int param_3 = obj->top();
49 * int param_4 = obj->getMin();
50 */
51
1let stack: number[] = []; // This is the primary stack for storing numbers.
2let minStack: number[] = [Infinity]; // This stack keeps track of the minimum values.
3
4/**
5 * Pushes a number onto the stack and updates the minStack appropriately.
6 * @param {number} val - The value to be pushed onto the stack.
7 */
8function push(val: number): void {
9 stack.push(val);
10 minStack.push(Math.min(val, minStack[minStack.length - 1]));
11}
12
13/**
14 * Removes the element on top of the stack and also updates the minStack.
15 */
16function pop(): void {
17 stack.pop();
18 minStack.pop();
19}
20
21/**
22 * Retrieves the element on top of the stack.
23 * @return {number} The top element of the stack.
24 */
25function top(): number {
26 return stack[stack.length - 1];
27}
28
29/**
30 * Retrieves the minimum element from the stack.
31 * @return {number} The current minimum value in the stack.
32 */
33function getMin(): number {
34 return minStack[minStack.length - 1];
35}
36
Time and Space Complexity
The provided Python code defines a class MinStack
which implements a stack that, in addition to the typical push and pop operations, can retrieve the smallest element in the stack in constant time.
Time Complexity:
__init__
: Initializing theMinStack
involves setting up two lists (stacks), which is anO(1)
operation.push
: This method appends a new element to thestk1
and computes the minimum with the last element ofstk2
to append tostk2
. Both operations areO(1)
since appending to a list in Python and retrieving the last element have constant time complexity.pop
: Here, we pop from bothstk1
andstk2
, which areO(1)
operations since popping from the end of a list in Python has constant time complexity.top
: This method simply returns the last element ofstk1
, which is anO(1)
operation.getMin
: Returning the last element ofstk2
, which is the current minimum, is also anO(1)
operation.
Overall, all of the operations of the MinStack
class run in constant time, so we have O(1)
time complexity for push, pop, top, and getMin methods.
Space Complexity:
- The space complexity of the
MinStack
class is mainly due to the space used by the two stacksstk1
andstk2
. Assumingn
is the number of elements pushed into the stack:stk1
grows linearly with the number of elements pushed, so it has a space complexity ofO(n)
.stk2
also grows with each push operation. Even though it's used to keep the minimum value at each state, it does in pair with thestk1
, so its size also corresponds to the number of elements pushed, which makes itO(n)
as well.
Therefore, the overall space complexity of the MinStack
class is O(n)
where n
is the number of elements in the stack.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.