# Min Stack

## Question ([LC.155](https://leetcode.com/problems/min-stack/description/))

> Design a data structure that supports push(x), pop(), top(), and getMin() all in O(1) time.

## Example

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

## Analysis

Besides the standard stack operations push(x), pop(), and peek(), we also need to support a heap operation getMin() in O(1) time. The first thought can be use a variable to keep track of the minimum value that works but when the min value gets popped out, we need to restore the second smallest value. This insight calls for a special type of stack - monotonic stack.

## Monotonic Stack

A monotonic stack is a stack in which its elements are strictly increasing or decreasing. In this case, we want to use a decreasing stack to keep track of all the min values.

## Illustration

We can use the example above.

```
push(-2) // stack.push(-2) if (decStack.isEmpty()) decStack.push(-2)
push(0) // stack.push(0) if (0 <= decStack.peek()) decStack.push(0)
push(-3) // stack.push(-3) if (-3 <= decStack.peek()) decStack.push(-3)

stack [-2, 0, -3]
decStack [-2, -3]

getMin() // return decStack.peek()
pop() // if (stack.pop() == decStack.peek()) decStack.pop()
top() // return stack.peek()
getMin() // return decStack.peek()
```

## Implementation

```java
class MinStack {    
    Stack<Integer> stack;
    Stack<Integer> decStack;

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

    public void push(int x) {
        stack.push(x);
        if (decStack.isEmpty() || x <= decStack.peek()) {
            decStack.push(x);
        }
    }

    public void pop() {
        if (stack.pop().equals(decStack.peek())) {
            decStack.pop();
        }
    }

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

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

## Max Stack ([LC.716](https://leetcode.com/problems/max-stack/description/))

> Design a data structure that supports push(x), pop(), top(), peekMax() and popMax().

## Analysis

In addition to function like a normal max stack, its an additional function popMax().\
Let's implement the normal functionalities first, then look into popMax().\
It turns we really just have to brute force this with two stacks. Using a temp stack to store the elements until we find max and pop it. The tricky part is that we have to push it back and update incStack.

Consider example

```
["MaxStack","push","push","popMax","peekMax"]
[[],[5],[1],[],[]]

stack [1]
incStack [!]
```

## Code

```java
class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> incStack;    

    public MaxStack() {
        stack = new Stack<Integer>();
        incStack = new Stack<Integer>();        
    }

    public void push(int x) {
        stack.push(x);
        if (incStack.isEmpty() || x >= incStack.peek()) {
            incStack.push(x);
        }        
    }

    public int pop() {
        int pop = stack.pop();
        if (pop == incStack.peek()) {
            incStack.pop();
        }
        return pop;
    }

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

    public int peekMax() {
        return incStack.peek();
    }

    public int popMax() {
        if (stack.isEmpty()) {
            return -1;
        }
        int max = incStack.pop();
        removeMax(max); // remove max from stack and update incStack
        return max;
    }

    // remove the max value from stack
    private void removeMax(int max) {
        // temp will store all the elements that are not max
        Stack<Integer> temp = new Stack<>();
        while (stack.peek() != max) {
            temp.push(stack.pop());
        }
        // found the max
        stack.pop();
        // push these elements back
        while (!temp.isEmpty()) {
            push(temp.pop().intValue());
        }
    }
}
```


---

# Agent Instructions: 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://zedive.gitbook.io/project-l/part-1/basic_data_structure/stack/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.