Min Stack Get Operation Implementation in O(1) Time Complexity

In this post, we are going to look at the Min Stack Get Operation problem. As the name itself suggests, this problem is about implementing an operation on Stack that allows the consumer to fetch the minimum element.

So what’s so hard about it?

Well – the catch here is to implement this operation in O(1) time complexity. In other words, constant time complexity.

So let’s look at the solution.

If you would like to watch a video instead of reading, you can head over to my YouTube channel where we walk through the same problem.

1 – The Approach for Min Stack Get

As we all know, Stack is a LIFO or Last in First out data structure. In other words, the latest element to get into the stack is the first one to get out.

If you wish to know more about Stacks, I have a detailed post about Stack Implementation.

Due to this LIFO property of Stack, there is no way we can directly return the minimum element. We can, of course, search the entire stack and find the smallest element. However, that approach has a linear time complexity i.e. O(n).

But we want to implement this method in O(1) time complexity.

1.1 – The First Approach

For starters, we can keep a track of the minimum value at all times using an independent variable. The below illustration shows such an approach.

The downside to this approach is that once we start popping elements from the stack, our min element might change.

For example, if we pop element 5 and then 1 from the above stack, our minimum element is no longer 1. And we will have to recalculate it by checking all the remaining elements in the stack. Such an operation will have time complexity of O(n).

1.2 – The Second Approach

Another approach is to preserve the state along with each element in the stack.

Let’s consider the same stack as the previous example. When 2 is inserted into the stack, the minimum element is also 2. So we store that information with the node itself. Next, when we insert 4, the minimum element is still 2.

However, once we store 1, the min element becomes 1 and at that point, we store the minimum element with the node itself. When we insert 5, the minimum element is still 1 and we store the same.

Below is how our stack will appear.

In the above case, each node knows what is the minimum element currently in the stack. So we can always get the min element in constant time complexity.

However, the downside to this approach is that it will double the space required to store the stack. In other words, for each element, there is a corresponding min value that we have to store. The space complexity of this solution is much higher than what we would like to.

We can do better and that’s where the next approach comes in.

1.3 – The Third Approach

Due to the drawback described previously, we arrive at the third solution. Instead of keeping the minimum value with every node in the stack, we create a separate stack to keep track of the minimum value.

Below is how such an implementation would look like:

As you can see, we have two stacks. The main stack or the item stack stores the values. However, the second stack also known as the min stack stores the minimum elements.

So how does it work in this case?

Suppose we start popping elements from the item stack. We first pop element 5. In that case, we check in the min stack whether the top element is same. Since 5 is not the top element in min stack, we simply continue.

Next, we pop the element 1. At this point, we again check the top element in the min stack. Since it is a match, we also pop element 1 from the min stack. This is because after 1 is out of the item stack, the minimum element in the remaining stack is 2.

This way we always know that the top element in the min stack is the smallest element. In case, we receive a min stack get request from the consumer, we can very easily return the value of the top element from the min stack. And such an operation will be in O(1) time complexity.

Also, in this approach, our space complexity is very less as compared with approach 2. This is because we are only storing the potential minimum elements in the second stack.

2 – Implementation Code

Below is the implementation code for approach 3. It is also available on this Gist.

The above code is in Javascript. Here, we have implemented our own Node class and Stack class. But the same concept can be extended to any other programming language.

To create a Stack, we are internally using a Linked List. The ItemStack holds the actual values whereas the MinStack is responsible for the minimum values.

---

With this, we have successfully implemented Min Stack Get Operation with O(1) time complexity.

If you have any comments or queries, please write them in the comments section below.