Leetcode 155. Min Stack
Problem Explanation
The problem requires you to design a stack which in addition to push, pop and top operations, has a min operation that can retrieve the minimum item currently in the stack in constant time.
Walkthrough
Letโs suppose we have a stack and we perform the following operations:
push(-2)
: Now our stack is [-2]push(0)
: Now our stack is [-2, 0]push(-3)
: Now our stack is [-2, 0, -3]getMin()
: This would return -3, which is the minimum element in the stack.pop()
: This would remove -3 from the stack causing it to become [-2, 0]top()
: This would return 0, which is the topmost element in the stack.getMin()
: This would return -2, which is the current minimum element in the stack.
Solution Approach
The standard stack in STL library only supports basic operations such as push, pop and top. To support the additional getMin()
operation, we'll modify our stack to store a pair of integers instead of a single integer.
In each pair, the first element will represent our original stack element and the second element will store the minimum element found so far. Thus whenever a new element is pushed into the stack, we compare it with the current minimum and push the lesser of the two as the new minimum.
Python Solution
1 2python 3class MinStack: 4 5 def __init__(self): 6 self.stack = [] 7 8 def push(self, x: int) -> None: 9 # If stack is empty then the min value can only be itself 10 if not self.stack: 11 self.stack.append((x, x)) 12 else: 13 # Check x against the current min in the stack 14 # the min value is the second item of the last element in the stack 15 current_min = self.stack[-1][1] 16 self.stack.append((x, min(x, current_min))) 17 18 def pop(self) -> None: 19 self.stack.pop() 20 21 def top(self) -> int: 22 return self.stack[-1][0] 23 24 def getMin(self) -> int: 25 return self.stack[-1][1]
Java Solution
1
2java
3class MinStack {
4
5 private Stack<int[]> stack = new Stack<>();
6
7 public MinStack() { }
8
9 public void push(int x) {
10 if (stack.isEmpty()) {
11 stack.push(new int[]{x, x});
12 } else {
13 int currentMin = stack.peek()[1];
14 stack.push(new int[]{x, Math.min(x, currentMin)});
15 }
16 }
17
18 public void pop() {
19 stack.pop();
20 }
21
22 public int top() {
23 return stack.peek()[0];
24 }
25
26 public int getMin() {
27 return stack.peek()[1];
28 }
29}
JavaScript Solution
1 2javascript 3var MinStack = function() { 4 this.stack = []; 5}; 6 7MinStack.prototype.push = function(x) { 8 if (this.stack.length === 0) { 9 this.stack.push([x, x]); 10 } else { 11 var currentMin = this.stack[this.stack.length-1][1]; 12 this.stack.push([x, Math.min(x, currentMin)]); 13 } 14}; 15 16MinStack.prototype.pop = function() { 17 this.stack.pop(); 18}; 19 20MinStack.prototype.top = function() { 21 return this.stack[this.stack.length-1][0]; 22}; 23 24MinStack.prototype.getMin = function() { 25 return this.stack[this.stack.length-1][1]; 26};
C++ Solution
1
2cpp
3class MinStack {
4public:
5 stack<pair<int, int>> s;
6
7 MinStack() {
8
9 }
10
11 void push(int x) {
12 if (s.empty()){
13 s.emplace(x,x);
14 } else {
15 s.emplace(x,min(x,s.top().second));
16 }
17 }
18
19 void pop() {
20 s.pop();
21 }
22
23 int top() {
24 return s.top().first;
25 }
26
27 int getMin() {
28 return s.top().second;
29 }
30};
C# Solution
1
2csharp
3public class MinStack {
4 private Stack<int[]> stack = new Stack<int[]>();
5
6 public MinStack() {
7 }
8
9 public void Push(int x) {
10 if (stack.Count == 0) {
11 stack.Push(new int[]{x, x});
12 } else {
13 int currentMin = stack.Peek()[1];
14 stack.Push(new int[]{x, Math.Min(x, currentMin)});
15 }
16 }
17
18 public void Pop() {
19 stack.Pop();
20 }
21
22 public int Top() {
23 return stack.Peek()[0];
24 }
25
26 public int GetMin() {
27 return stack.Peek()[1];
28 }
29}
Rust Solution
In Rust, we can use Vec to simulate stack because Vec has push
and pop
operations. Here is the code for the problem in Rust:
1
2rust
3pub struct MinStack {
4 stack: Vec<(i32, i32)>,
5}
6
7impl MinStack {
8 pub fn new() -> Self {
9 MinStack { stack: Vec::new() }
10 }
11
12 pub fn push(&mut self, x: i32) {
13 let min = match self.stack.last() {
14 None => x,
15 Some(&(_, min)) => std::cmp::min(min, x),
16 };
17 self.stack.push((x, min));
18 }
19
20 pub fn pop(&mut self) {
21 self.stack.pop();
22 }
23
24 pub fn top(&self) -> i32 {
25 self.stack.last().unwrap().0
26 }
27
28 pub fn get_min(&self) -> i32 {
29 self.stack.last().unwrap().1
30 }
31}
Go Solution
In Go, we use slices to implement the stack because slices have append
and len
properties which allow us to simulate push
and pop
behavior. Here is the Go solution:
1 2go 3type MinStack struct { 4 stack []int 5 minStack []int 6} 7 8func Constructor() MinStack { 9 return MinStack{} 10} 11 12func (this *MinStack) Push(x int) { 13 this.stack = append(this.stack, x) 14 if len(this.minStack) == 0 || x <= this.getMin() { 15 this.minStack = append(this.minStack, x) 16 } 17} 18 19func (this *MinStack) Pop() { 20 if this.top() == this.getMin() { 21 this.minStack = this.minStack[:len(this.minStack)-1] 22 } 23 this.stack = this.stack[:len(this.stack)-1] 24} 25 26func (this *MinStack) Top() int { 27 return this.stack[len(this.stack)-1] 28} 29 30func (this *MinStack) GetMin() int { 31 return this.minStack[len(this.minStack)-1] 32}
In each of the above examples, we are maintaining a pair of values at each index of our stack data structure. This pair contains the main stack value at the first index, and the minimum seen so far at the second index. With this design, we're able to keep track of the minimum value in the stack regardless of the order or number of elements added or removed.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.