# Min Stack
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/min-stack)
Canonical: https://scaleengineer.com/dsa/problems/min-stack
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Stack
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Snowflake](https://scaleengineer.com/companies/snowflake), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [Lucid Motors](https://scaleengineer.com/companies/lucid-motors), [Lyft](https://scaleengineer.com/companies/lyft), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Nike](https://scaleengineer.com/companies/nike), [Salesforce](https://scaleengineer.com/companies/salesforce), [Veeva Systems](https://scaleengineer.com/companies/veeva-systems), [Snap](https://scaleengineer.com/companies/snap), [Zenefits](https://scaleengineer.com/companies/zenefits), [Vimeo](https://scaleengineer.com/companies/vimeo), [Odoo](https://scaleengineer.com/companies/odoo), [Informatica](https://scaleengineer.com/companies/informatica), [Delhivery](https://scaleengineer.com/companies/delhivery), [IMC](https://scaleengineer.com/companies/imc)
---
## Problem
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.

**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

**Constraints:**

* `-231 <= val <= 231 - 1`
* Methods `pop`, `top` and `getMin` operations will always be called on **non-empty** stacks.
* At most `3 * 104` calls will be made to `push`, `pop`, `top`, and `getMin`.

# Approaches
## Approach 1: Stack of Value/Minimum Pairs
This approach uses a single stack, but instead of storing just the integer values, it stores a pair of integers for each entry. Each pair consists of the value itself and the minimum value in the stack at the time of the push operation. This ensures that the minimum element is always available at the top of the stack, along with the actual top element.
**Time:** O(1) · **Space:** O(N)
**Pros:** Conceptually straightforward.; All operations are guaranteed O(1) time.; Encapsulates all required information within a single data structure.
**Cons:** Uses significantly more space than other O(1) time solutions, as it stores a minimum value for every single element pushed onto the stack.
### Explanation
To implement this, we can create a helper class or a record to store the pair `(value, min)`. When we push a new element `val`, we look at the minimum of the current top element. The new minimum to be stored with `val` will be `Math.min(val, stack.peek().min)`. If the stack is empty, the minimum is just `val`. This way, the `min` part of the top pair always holds the minimum value of the entire stack. The `getMin()` operation becomes trivial: just peek at the top element and return its stored minimum. `pop()` and `top()` also remain simple, operating on the pairs.

```java
class MinStack {
    // Inner class to store the value and the minimum at that point
    private class Node {
        int val;
        int min;

        Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    private Stack<Node> stack;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        int currentMin;
        if (stack.isEmpty()) {
            currentMin = val;
        } else {
            // The new minimum is the minimum of the new value and the previous minimum
            currentMin = Math.min(val, stack.peek().min);
        }
        stack.push(new Node(val, currentMin));
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek().val;
    }

    public int getMin() {
        return stack.peek().min;
    }
}
```
### Algorithm
- **Data Structure**: Use a single stack where each element is a pair `(value, current_minimum)`.
- **`push(val)`**:
  - If the stack is empty, the new minimum is `val` itself.
  - Otherwise, the new minimum is the smaller value between `val` and the minimum of the element currently at the top of the stack.
  - Push a new pair `(val, new_minimum)` onto the stack.
- **`pop()`**:
  - Simply pop the top pair from the stack.
- **`top()`**:
  - Peek at the top pair and return its `value` component.
- **`getMin()`**:
  - Peek at the top pair and return its `current_minimum` component.

## Approach 2: Two Stacks
A classic and highly intuitive solution involves using two stacks. One stack, the main stack, behaves like a normal stack and holds all the elements. The second stack, the "min stack," is used exclusively to keep track of the current minimum element. The top of the min stack is always the minimum element in the main stack.
**Time:** O(1) · **Space:** O(N)
**Pros:** Achieves O(1) time complexity for all operations.; More space-efficient on average than the pair approach, as the min stack only grows when a new, smaller element is added.
**Cons:** Requires managing two separate data structures.; In the worst-case scenario (pushing elements in a strictly decreasing order), the space complexity is O(N), same as the less efficient pair approach.
### Explanation
When we push a new element `val`, it always goes into the main stack. We then compare `val` with the element at the top of the `minStack`. If `val` is less than or equal to the current minimum, it represents a new minimum (or an equally small value), so we push it onto the `minStack`. The "equal to" condition is crucial for handling cases with duplicate minimum values. When we pop an element, we check if the popped element is the same as the one at the top of the `minStack`. If it is, we must also pop from the `minStack` to expose the next-smallest minimum. This ensures that `getMin()` can always return the correct minimum in O(1) time by simply peeking at the `minStack`.

```java
import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        // Push to minStack only if it's a new minimum or equal to the current minimum
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        int popped = stack.pop();
        // If the popped element was the minimum, remove it from minStack as well
        if (popped == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
```
### Algorithm
- **Data Structures**: Use a primary stack (`stack`) for all elements and a secondary stack (`minStack`) to track minimums.
- **`push(val)`**:
  - Always push `val` onto the `stack`.
  - If `minStack` is empty or `val` is less than or equal to the value at the top of `minStack`, push `val` onto `minStack` as well.
- **`pop()`**:
  - Pop the top element from `stack`.
  - If the popped value is equal to the top of `minStack`, pop from `minStack` too.
- **`top()`**:
  - Return the top of `stack`.
- **`getMin()`**:
  - Return the top of `minStack`.

## Approach 3: Space-Optimized Single Stack
This is the most space-optimized approach that maintains O(1) time complexity for all operations. It uses only a single stack and one extra variable to keep track of the minimum. Instead of storing the actual values on the stack, we store the difference (or "gap") between the pushed value and the current minimum value. This encoding allows us to deduce the actual value and restore previous minimums during pop operations.
**Time:** O(1) · **Space:** O(N)
**Pros:** Extremely space-efficient, using O(1) extra space besides the stack itself.; All operations are O(1) time complexity.
**Cons:** The logic is significantly more complex and less intuitive than other approaches.; Requires careful handling of data types (using `long`) to prevent integer overflow when calculating differences.
### Explanation
We maintain a variable `min` that holds the current minimum value in the stack. The stack itself will store `long` values to avoid overflow since the difference between two `int` values can exceed the `int` range.

When pushing a value `val`, we push the difference `(long)val - min` onto the stack. If `val` is smaller than the current `min`, we update `min` to `val`.

When popping, if the popped difference is negative, it signifies that the element being removed was a minimum. The value of `min` before this element was pushed can be recovered using the formula `previous_min = current_min - diff`. We update `min` to this restored value. If the difference is non-negative, the `min` value is unaffected.

The `top` operation similarly uses the difference at the top of the stack to calculate the actual top value relative to the current `min`.

```java
import java.util.Stack;

class MinStack {
    private Stack<Long> stack;
    private long min;

    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = val;
        } else {
            long diff = (long)val - min;
            stack.push(diff);
            if (diff < 0) {
                // New value is the new min
                min = val;
            }
        }
    }

    public void pop() {
        long diff = stack.pop();
        if (diff < 0) {
            // The popped element was a minimum. Restore the previous minimum.
            // previous_min = current_min - diff
            min = min - diff;
        }
    }

    public int top() {
        long diff = stack.peek();
        if (diff < 0) {
            // The top element is the current minimum
            return (int)min;
        } else {
            // Reconstruct the original value: val = min + diff
            return (int)(min + diff);
        }
    }

    public int getMin() {
        return (int)min;
    }
}
```
### Algorithm
- **Data Structures**: Use a single `Stack<Long>` and a `long min` variable.
- **`push(val)`**:
  - If the stack is empty, push `0L` and set `min = val`.
  - Otherwise, calculate the difference `diff = (long)val - min`. Push `diff` onto the stack.
  - If `val < min`, update `min = val`.
- **`pop()`**:
  - Pop `diff` from the stack.
  - If `diff < 0`, it means the minimum element was just popped. Restore the previous minimum by updating `min = min - diff`.
- **`top()`**:
  - Peek at `diff` from the stack.
  - If `diff < 0`, the actual top value is the current `min`.
  - Otherwise, the actual top value is `min + diff`.
- **`getMin()`**:
  - Return the current value of the `min` variable.

# Solutions
### CSharp

```csharp
public class MinStack { private Stack < int > stk1 = new Stack < int >(); private Stack < int > stk2 = new Stack < int >(); public MinStack () { stk2 . Push ( int . MaxValue ); } public void Push ( int x ) { stk1 . Push ( x ); stk2 . Push ( Math . Min ( x , GetMin ())); } public void Pop () { stk1 . Pop (); stk2 . Pop (); } public int Top () { return stk1 . Peek (); } public int GetMin () { return stk2 . Peek (); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.Push(x); * obj.Pop(); * int param_3 = obj.Top(); * int param_4 = obj.GetMin(); */
```

### Java

```java
class MinStack { private Deque < Integer > stk1 = new ArrayDeque <>(); private Deque < Integer > stk2 = new ArrayDeque <>(); public MinStack () { stk2 . push ( Integer . MAX_VALUE ); } public void push ( int val ) { stk1 . push ( val ); stk2 . push ( Math . min ( val , stk2 . peek ())); } public void pop () { stk1 . pop (); stk2 . pop (); } public int top () { return stk1 . peek (); } public int getMin () { return stk2 . peek (); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(val); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */
```

### JavaScript

```javascript
var MinStack = function () { this . stk1 = []; this . stk2 = [ Infinity ]; }; /** * @param {number} val * @return {void} */ MinStack . prototype . push = function ( val ) { this . stk1 . push ( val ); this . stk2 . push ( Math . min ( this . stk2 [ this . stk2 . length - 1 ], val )); }; /** * @return {void} */ MinStack . prototype . pop = function () { this . stk1 . pop (); this . stk2 . pop (); }; /** * @return {number} */ MinStack . prototype . top = function () { return this . stk1 [ this . stk1 . length - 1 ]; }; /** * @return {number} */ MinStack . prototype . getMin = function () { return this . stk2 [ this . stk2 . length - 1 ]; }; /** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(val) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.getMin() */
```

### CPP

```cpp
class MinStack { public: MinStack () { stk2 . push ( INT_MAX ); } void push ( int val ) { stk1 . push ( val ); stk2 . push ( min ( val , stk2 . top ())); } void pop () { stk1 . pop (); stk2 . pop (); } int top () { return stk1 . top (); } int getMin () { return stk2 . top (); } private: stack < int > stk1 ; stack < int > stk2 ; }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
```

### Python

```python
class MinStack : def __init__ ( self ): self . sk = [] self . minsk = [ inf ] # trick, avoid later empty-check for min-stack def push ( self , x : int ) -> None : self . sk . append ( x ) self . minsk . append ( min ( x , self . minsk [ - 1 ])) def pop ( self ) -> None : if not self . sk : return self . sk . pop () self . minsk . pop () def top ( self ) -> int : return self . sk [ - 1 ] def getMin ( self ) -> int : return self . minsk [ - 1 ] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin() ############ class MinStack : def __init__ ( self ): self . sk = [] self . minsk = [] def push ( self , val : int ) -> None : self . sk . append ( val ) # empty check self . minsk . append ( val if not self . minsk else min ( val , self . minsk [ - 1 ])) def pop ( self ) -> None : if not self . sk : return self . sk . pop () self . minsk . pop () def top ( self ) -> int : return self . sk [ - 1 ] def getMin ( self ) -> int : return self . minsk [ - 1 ] # optimize above, using only 1 stack, with stack element as tuple: (val, its associated min) class MinStack : def __init__ ( self ): self . _stack = [] def push ( self , x : int ) -> None : cur_min = self . getMin () if x < cur_min : cur_min = x self . _stack . append (( x , cur_min )) def pop ( self ) -> None : self . _stack . pop () def top ( self ) -> int : if not self . _stack : return None else : return self . _stack [ - 1 ][ 0 ] def getMin ( self ) -> int : if not self . _stack : return float ( 'inf' ) else : return self . _stack [ - 1 ][ 1 ]
```