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.