Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

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:

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

3.2. Two-stack Algorithm

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

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!