## Min Stack Problem

**Difficulty**: Easy

**Asked in**: Amazon, Microsoft, Yahoo, Adobe

#### Understanding the Problem:

Given Problem is to design a special stack data structure such that it supports following operations in constant O(1) time complexity.

**top():**which will get the top element of the stack.**getMin():**returns the minimum elements of the stack (Currently present, deleted ones are not taken into account).**push(element):**pushes an element "element" in the stack.**pop():**removes the element present at the top from the stack.

**For Example:**

```
Input:
stck = minStack() //Create an object of your special stack
stck.push(2)
stck.push(4)
stck.top() ----------> returns 4 as 4 is at the top(last inserted element)
stck.getMin() -------> returns 2 as it is the current minimum
stck.pop()
stck.push(-1)
stck.getMin() -------> returns -1 as now it is the minimum element.
```

**Possible questions to ask the interviewer: →**

- Can I use extra space for solving this? (
**Ans:**Yes, you can. Try to optimise it though. Make sure time complexity is constant.**)** - What will be the input format? (
**Ans:***The input provided will be a series of function calls like push(), pop(), top(), getMin(), etc.***)**

You can try solving this problem here and then move on to the solution part.

#### Solutions

So here we are going to discuss two possible solutions to solve this problem. Both the solutions will be of constant time complexity. However, the second solution will be more optimised in terms of space and will be testing your mathematical skills. Excited? Let’s see both the solutions in details.

**Solution 1:**Using Extra Space**Solution 2:**Using Constant Space

**Using Extra Space**

This approach will use an array which will be used to store elements at every point whenever its value is less than the top element of the stack. So we will keep checking every time before pushing the element into the stack(`push()`

operation) if its value is smaller than the last element inserted into the array or not. If yes, we will add this element to the array as well as to the stack. Else, we will only add the element to the stack.

In case of the `pop()`

operation, we will check if the element to be deleted(top element) is the same as the last element inserted to the array. If this is the case, we have to delete this element from both the places(stack and array) so that the last element of the array now will point to the current minimum element.

The `top()`

operation will simply return the last element present in the stack and the `getMin()`

operation will return the last element of the array.

**Solution steps**

- We will create an array to store all the current minimum values so to access it accordingly.
- During the push operation, we will push the element ‘elem’ directly to the stack and array if the stack is empty. If not, then we will compare the ‘elem’ with the last inserted element in the stack. If it is smaller we will push it to both stack and array. Else, will push only into the stack.
- In the pop operation, we will check if the last inserted element is same as the last pushed element in the array. If yes, we will need to delete both of them so that the last element of the array will now be pointing to the current minimum element after the deletion of this(top) element.
- For top operation and getMin operation, we simply need to return the last element of the stack and the array respectively.

**Pseudo-code**

```
class MinStack {
public:
vector <int> stack
vector <int> minArray
MinStack() {
//Constructor
}
//Push operation
void push(int elem) {
if(!minArray.empty())
{
if(elem <= minArray.back())
minArray.push_back(elem)
}
else
minArray.push_back(elem)
stack.push_back(elem)
}
//Pop operation
void pop() {
if(stack.back() == minArray.back())
{
minArray.pop_back()
}
stack.pop_back()
}
//Top operation
int top() {
if(!stack.empty()) //Simply returns top element from stack
return stack.back()
else
return -1
}
//getMin operation
int getMin() {
if(!minArray.empty()) //Simply returns last element from //minArray
return minArray.back()
else
return -1
}
}
```

Note: Vectors are dynamic arrays supported by C++ STL. push_back(T elem) will push an element to vector, pop_back() will delete the last element, empty() will check if the vector is empty or not and back() will give the last element of the vector. For getting more idea: — Go here. You can find its subtitute in whaever language you code.

**Complexity Analysis**

Time Complexity: O(1)

Space Complexity: O(N)

**Critical ideas to think!**

- What if instead of having an array, we keep only one variable for minimum Element and keep updating it with every push operation if the new element is smaller than the current minimum element? Do you see any issues in this approach?
**(Think and comment down below)**

**Using Constant Space**

In this approach instead of using an array and increasing the space complexity, we will rather use a variable `minElement`

which will store the current minimum element of the stack at every point.

Have you thought about the above given critical idea? Hmm, the problem is when we have to `pop`

this `minElement`

from the stack. How will we update the minElem then?

To solve this issue, we will use a very different idea. The idea is to whenever we will encounter an element smaller than minElement instead of pushing the ‘elem’ to the stack and updating `minElement`

, we will instead push (2*elem - minElement) to the stack and update `minElement`

with ‘elem’.

During the pop operation, if we encounter any element smaller than `minElement`

, we will know it is the same altered element that we pushed and it’s time to modify our `minElement`

. We will return the `minElement`

and update our `minElement`

with (2*minElement - top Element). Too many maths involved here. Let's move on to the solution steps.

**Solution steps**

- We will modify our push operation such that it simply pushes the element and update
`minElement`

if the stack is empty. Otherwise, it will compare the ‘elem’ with the`minElement`

. If smaller, we will push (2*elem-minElement) instead to the stack and update`minElement`

with ‘elem’. - Similarly, we will modify our pop operation so that whenever we will encounter that that top element to be deleted is less than
`minElement`

, we will update our minElement with (2*minElement-top element). - For top operation, we will check if the last inserted element of the stack is smaller than
`minElement`

. If yes, we will return`minElement`

. Else we will return the last element pushed into the stack.**(Think why?)** - For
`getMin`

operation, we will simply return the value of`minElement`

.

**Illustration for this solution**

We will take the above approach and will insert 2, 4, -1 into the stack.

```
Insert 2 →stack is empty simply push 2. minElement is 2
Insert 4 → 4 > 2, push 4 to stack. minElement is still 2.
Insert -1, -1 < 2, push (2*elem — minElement) i.e. -4 to the stack. minElement is -1.
Pop top element i.e. -4, it is the time to change our minElement. minElement will be 2*minElement- top Element i.e. 2*-1-(-4) = 2.
Wow, that is exactly what we want.
```

**Why this approach works?**

If you have observed, we have taken two assumptions:

- (2*elem-minElement) < minElement and,
- previous
`minElement`

was (2*minElement - y) which was used to make new`minElement`

after deleting y, where y is the smaller number than current minElement that is to be deleted(pop operation).

**Let us try to prove this using mathematics:**

**Proving our point (i)**

```
For simplicity let us take elem as e, minElement as m, previous minElement as p
e < m which implies e-m < 0
//Adding e to both sides
2*e - m < e
Thus, we can conclude:
2*elem - minElement < elem
```

**Proving our point (ii)**

```
//For simplicity let us take elem as e, minElement as m, previous minElement as p and n for new minElement
We know y was pushed as 2*e - p when e < current minElement
y = 2*e - p
// minElement was updated to e
m = e
n = 2*m - y
= 2*e - (2*e - p)
= p
So the new minElement is equal to previous minElement.
Hurrah! This is what we wanted.
```

**Pseudo-code**

```
class MinStack {
public:
vector <long int> stack
long int minimum
MinStack() {
//Constructor
}
//Push Operation
void push(int x) {
long y = (long)x
if(!stack.empty())
{
if(y<minimum) {
stack.push_back(2*y - minimum)
minimum = y
}
else
stack.push_back(y)
}
else {
stack.push_back(y)
minimum =y
}
}
//Pop Operation
void pop() {
if(stack.back() < minimum)
{
minimum = 2*minimum - stack.back();
stack.pop_back()
}
else
stack.pop_back()
}
//Top Operation
int top() {
if(!stack.empty())
if(stack.back() < minimum)
return minimum
else
return stack.back()
else
return -1
}
//getMin Operation
int getMin() {
return minimum
}
};
```

Complexity Analysis

**Time Complexity:** O(1)

**Space Complexity:** O(1)

**Critical ideas to think!**

- Can you think of problems that can be solved using a similar approach? Think and implement problems based on this approach.

#### Comparison Table for Above Solutions

#### Suggested Problems to Solve

- Find the maximum element in the Stack in constant time.
- Find duplicates in an array in O(N) time and constant space.
- Clone a stack without using extra space.
- Design a data structure that supports insert, delete, search and getRandom in constant time.
- Merge two sorted arrays in constant space.

**Happy Coding!!!**