Minimum Stack With O(1) Time | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll show how to get the minimum element from a stack in $O(1)$ time.

2. Problem Description

Design a number stack that supports regular stack operations of $push$ , $pop$ , $top$ , and an additional operation $getMin$ which should return the minimum element from the stack.

Suppose we have 3 numbers $\{5, 6, 3\}$ . When we push the first number 5 into the stack, the stack top and minimum is 5:

When we push the number 6 into the stack, the stack top becomes 6, but the minimum is still 5:

When we push the number 3 into the stack, both the stack top and minimum become 3:

If we pop the top number 3, The minimum number is changed back to 5:

3. Two-stack Solution

We can use two stacks to construct the special minimum stack. The first stack, $mainStack$ , stores all the elements. The second stack, $minStack$ , keeps track of the minimum numbers.

The top of the $mainStack$ contains the top element of the stack. Also, we can access the minimum element from the top of the $minStack$ .

3.1. Two-stack Example

In our example, when we push the first number 5, we push it into both stacks:

When we push the number 6, the top of $mainStack$ becomes 6. However, we don’t push it into $minStack$ because it is greater than the current minimum 5:

When we push the number 3, we push it into both stacks, as 3 is the new minimum number:

If we pop the number 3, we pop it from both stacks as 3 is the current minimum number:

3.2. Two-stack Algorithm

Based on the above example, we can use two stacks to implement $push$ , $pop$ , $top$ and $getMin$ functions:

When we push a number, we also compare the number with the top of the $minStack$ . If the number is smaller than or equal to the current top of $minStack$ , we also push it into the $minStack$ . Similarly, we also compare the top numbers between $mainStack$ and $minStack$ when we pop a number. If they are the same, we also pop the number from the $minStack$ .

In this algorithm, all operations take $O(1)$ time. We use an extra stack to store the history of minimum numbers. Therefore, we need $O(n)$ space for the $getMin$ function.

4. One-stack Solution

In order to get the minimum number in $O(1)$ time, we need to keep the history of the minimum numbers. The two-stack solution uses an extra stack to achieve that. In the one-stack solution, we’ll track the history by a math calculation.

We use a single variable, $minValue$ , to store the current minimum value of the stack. If the stack is empty, we can push the number directly into the stack and set $minValue$ to the pushed number.

When we push a number, $value$ , into the non-empty stack, we first compare the number with the current minimum value, $minValue$ . If $value \ge minValue$ , we can push $value$ directly into the stack. The $minValue$ remains the same and the stack top value is the one we just pushed.

However, when we push a new minimum number, i.e., $value < minValue$ , we need to record this minimum value change at the stack position.

To record this minimum value change, we first need to differentiate this case with the case without the minimum value change, i.e., when $value \ge minValue$ . Therefore, we need to push a number that is less than the new minimum value into the stack. Also, we need to record the previous minimum value so that when we do $pop$ operation, we can recover this number as the current minimum value.

4.1. One-stack Idea

Let the $stackTopValue$ represent the number we push into the stack, $oldMinValue$ represent the previous minimum value, which is $minValue$ before the $push$ operation, and $newMinValue$ represent the updated minimum value, which is $value$ . We can use the following formula to calculate $stackTopValue$ :

Since $newMinValue$ is less than $oldMinValue$ , we have $newMinValue - oldMinValue < 0$ . Therefore, $stackTopValue < newMinValue$ . This means we push a number that is less than the new $minValue$ . In this way, we can know that this stack position indicates a $minValue$ change.

In this formula, we multiply $newMinValue$ with 2 so that $stackTopValue$ is always less than $newMinValue$ . If we just use $newMinValue - oldMinValue$ to calculate the $stackTopValue$ , we’ll have a bigger $stackTopValue$ for negative numbers.

For example, when we push a new minimum number -3 into the stack whose current minimum number is -2, we have

However, with the muplication of 2 on the $newMinValue$ , we have

When we do a $top$ operation, we compare the stack top with $minValue$ . If the stack top is less than $minValue$ , we can know that we made a minimum number change at this position. Therefore, we can return $minValue$ directly. Otherwise, we can just return the stack top as it is the real number, we pushed into the stack without the math transformation.

Similarly, when we do a $pop$ operation, we first compare the stack top with $minValue$ . If the stack top is less than $minValue$ , we need to restore the $minValue$ to the previous one. We can calculate the previous minimum value by reversing the above formula:

4.2. One-stack Example

In our example, when we push the first number 5, we push it into the stack and set $minValue$ to 5:

When we push the number 6, the top of $mainStack$ becomes 6. However, the $minValue$ remains the same since the pushed number is greater than it:

If we do $top$ operation at this time, we return the stack top value 6 as it is greater than the current $minValue$ .

When we push the number 3, we push the number $2 \times 3 - 5= 1$ into the stack. Also, we update the $minValue$ to be 3:

If we do $top$ operation at this time, we return $minValue$ , as the stack top value is less than $minValue$ .

If we do $pop$ operation, we pop the stack top and update the $minValue$ to be $2 \times 3 - 1=5$ :

4.3. One-stack Algorithm

Based on the above example, we can use one stack and an extra variable to implement $push$ , $pop$ , $top$ and $getMin$ functions:

In this algorithm, all operations take $O(1)$ time. Also, we use only one variable to store the minimum value. Therefore, we need $O(1)$ space for the $getMin$ function.

5. Conclusion

In this article, we showed two solutions to design a minimum stack with $O(1)$ time for regular stack operations and $getMin$ operation. With two stacks, we can achieve the design in a straightforward way. Also, we can reduce the memory requirement to $O(1)$ by using some math transformation on the pushed numbers.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex