> For the complete documentation index, see [llms.txt](https://chunhthanhde.gitbook.io/leetcode-top-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-7-stack/054-min-stack.md).

# 155. Min Stack 🗃️

**Difficulty**: `Medium` - **Tags**: `Stack`, `Design`

[LeetCode Problem Link](https://leetcode.com/problems/min-stack/)

***

## Problem Statement 📜

Design a stack that supports the following operations in constant time `O(1)`:

1. `void push(int val)`: Push the element `val` onto the stack.
2. `void pop()`: Remove the element on the top of the stack.
3. `int top()`: Retrieve the top element of the stack.
4. `int getMin()`: Retrieve the minimum element in the stack.

You must implement all these methods in constant time.

***

## Examples 🌟

🔹 **Example 1:**

**Input:**

```plaintext
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
```

**Output:**

```plaintext
[null,null,null,null,-3,null,0,-2]
```

**Explanation:**

```plaintext
MinStack minStack = new MinStack();
minStack.push(-2);    // Stack: [-2]
minStack.push(0);     // Stack: [-2, 0]
minStack.push(-3);    // Stack: [-2, 0, -3]
minStack.getMin();    // return -3
minStack.pop();       // Stack: [-2, 0]
minStack.top();       // return 0
minStack.getMin();    // return -2
```

***

## Constraints ⚙️

* `-2^31 <= val <= 2^31 - 1`
* Methods `pop`, `top`, and `getMin` will always be called on non-empty stacks.
* At most `3 * 10^4` calls will be made to `push`, `pop`, `top`, and `getMin`.

***

## Solution 💡

To achieve `O(1)` time complexity for all operations, we can use **two stacks**:

1. **Primary stack** to store all elements.
2. **Min stack** to keep track of the minimum value at each level of the stack.

For every `push`, we add the value to the primary stack, and update the min stack with the current minimum value. For `pop`, we remove from both stacks.

***

### Java Solution

```java
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 the current minimum to the minStack
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }

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

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

    public int getMin() {
        return minStack.peek();
    }
}
```

***

## Explanation of the Solution

1. **Two Stacks**:
   * The main stack holds all the elements.
   * The min stack maintains the current minimum at every point.
2. **Push Operation**:
   * Push the element onto the main stack.
   * Update the min stack with the smaller of the new element and the current minimum.
3. **Pop Operation**:
   * Remove the top element from both stacks.
4. **Top Operation**:
   * Return the top element of the main stack.
5. **GetMin Operation**:
   * Retrieve the top element of the min stack, which represents the minimum.

***

## Time Complexity ⏳

* **Push**: `O(1)`
* **Pop**: `O(1)`
* **Top**: `O(1)`
* **GetMin**: `O(1)`

## Space Complexity 💾

* **O(n)**: We use two stacks, each storing up to `n` elements.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%207%20Stack/054%20Min%20Stack/Solution.java).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-7-stack/054-min-stack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.