# Min Stack - LeetCode Problem

## Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the [Min Stack problem](https://leetcode.com/problems/min-stack/).

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

* `push(x)` -- Push element `x` onto stack.
    
* `pop()` -- Remove the element on top of the stack.
    
* `top()` -- Get the top element.
    
* `getMin()` -- Retrieve the minimum element in the stack.
    

That's it! Now, let's dive into the solution.

## Solution

We'll start by creating a stack class that contains a list and a minimum value. The list will hold the values that are pushed onto the stack, while the minimum value will keep track of the minimum value seen so far.

```python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_val = float('inf')
```

We'll then implement the `push()` method, which adds an element to the top of the stack. If the element being pushed is less than or equal to the current minimum value, we'll update the minimum value.

```python
def push(self, x: int) -> None:
    self.stack.append(x)
    if x <= self.min_val:
        self.min_val = x
```

Next, we'll implement the `pop()` method, which removes the element on top of the stack. If the element being popped is the minimum value, we'll need to update the minimum value to the next smallest value on the stack.

```python
def pop(self) -> None:
    if self.stack.pop() == self.min_val:
        self.min_val = min(self.stack) if self.stack else float('inf')
```

The `pop()` method first removes the top element from the stack using the `pop()` method. If the popped element is the minimum value, we'll need to update the minimum value. We'll check if the popped element is equal to the current minimum value, and if it is, we'll update the minimum value to the smallest value on the stack (if the stack is not empty) or `float('inf')` (if the stack is empty).

Next, we'll implement the `top()` method, which returns the top element of the stack. This method is straightforward, as it simply returns the last element of the stack.

```python
def top(self) -> int:
    return self.stack[-1]
```

Finally, we'll implement the `getMin()` method, which returns the minimum value in the stack. This method is also straightforward, as we've been keeping track of the minimum value as we push and pop elements from the stack.

```python
def getMin(self) -> int:
    return self.min_val
```

And there you have it! Here's the full code for our `MinStack` class:

```python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_val = float('inf')
    
    def push(self, x: int) -> None:
        self.stack.append(x)
        if x <= self.min_val:
            self.min_val = x
    
    def pop(self) -> None:
        if self.stack.pop() == self.min_val:
            self.min_val = min(self.stack) if self.stack else float('inf')
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_val
```

## Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

### Time Complexity

Our `push()`, `pop()`, `top()`, and `getMin()` methods all have a time complexity of `O(1)`, as they all perform constant time operations on the stack.

### Space Complexity

Our `MinStack` class uses a list to store the values pushed onto the stack, and a variable to store the minimum value seen so far. Therefore, the space complexity of our class is `O(n)`, where `n` is the number of elements pushed onto the stack.

## Conclusion

And there you have it! We've successfully tackled the Min Stack problem. I hope you found this blog post helpful and informative. Happy Coding! 😎