In this blog post, we'll explore the design and implementation of a special kind of stack called a MinStack. The MinStack supports the usual stack operations such as push, pop, and top, but it also provides a method to retrieve the minimum element in constant time, O(1).

## Understanding the Problem

Before diving into the implementation details, let's understand the problem statement.

We are required to implement the `MinStack`

class with the following functionalities:

`push(val)`

: Adds the element`val`

to the top of the stack.`pop()`

: Removes the element from the top of the stack.`top()`

: Returns the element present at the top of the stack without removing it.`getMin()`

: Returns the minimum element present in the stack.

The crucial requirement is that all these operations must have a time complexity of O(1).

## Approach

To achieve O(1) time complexity for all operations, we need to maintain additional information alongside the main stack. Specifically, we'll maintain a separate stack to keep track of the minimum element at any given point in the main stack.

Let's walk through the implementation provided in the code snippet and understand each method:

```
class MinStack:
def __init__(self):
# Initialize the main stack and the auxiliary stack to track minimums.
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
# Push the value onto the main stack.
self.stack.append(val)
# Update the minimum stack.
if self.minStack:
val = min(self.minStack[-1], val)
self.minStack.append(val)
def pop(self) -> None:
# Remove the top element from both the main stack and the minimum stack.
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
# Return the top element of the main stack.
return self.stack[-1]
def getMin(self) -> int:
# Return the top element of the minimum stack, which represents the minimum element in the main stack.
return self.minStack[-1]
```

## Explanation

**Initialization**:

- We initialize two empty stacks:
`stack`

to hold the main elements and`minStack`

to track the minimums.

**Push Operation ( push(val))**:

- We add the given value
`val`

to the main stack. - If the
`minStack`

is not empty, we compare the current value with the top element of`minStack`

to determine the new minimum value. - We then push this new minimum value onto the
`minStack`

.

**Pop Operation ( pop())**:

- We simply pop the top element from both the main stack and the
`minStack`

.

**Top Operation ( top())**:

- We return the top element of the main stack without removing it.

**Get Minimum Operation ( getMin())**:

- We return the top element of the
`minStack`

, which represents the minimum element present in the main stack.

## Conclusion

In conclusion, we have successfully designed and implemented a MinStack that supports all required operations in constant time complexity. By maintaining an additional stack to track the minimums, we've ensured efficient retrieval of the minimum element at any point. This solution is efficient and meets the requirements of the problem statement.