Min stack and max stack in Python

Why it matters

A stack gives you two cheap questions: what was added last, and what is on top. Programs often need a third answer as well: what is the smallest value in the stack right now? A system that keeps a stack of sensor readings may need the lowest reading kept so far, after every push and pop, without looking through the whole stack each time.

The naive answer is a scan. Look at every item and keep the smallest. In Python, min(values) does that scan for you. It is correct, but the time it takes grows with the number of items. If the program asks for the minimum after every push, the total work for n pushes is about n times n divided by 2, which is O(n squared). The method in this lesson answers the question in O(1), which means a fixed amount of work no matter how many items the stack holds. Push and pop stay O(1) too.

This lesson uses only a plain Python list as the stack. The same idea, with the comparison flipped, gives a max stack.

Words you will need

Stack: a list where you add and remove items at one end, called the top. Adding an item is a push, and removing the top item is a pop.
List: Python's built-in ordered collection, written with square brackets, such as [5, 3, 7]. A list can be used as a stack. append(x) adds x to the end, pop() removes the last item and returns it, and values[-1] reads the last item without removing it. The end of the list is the top of the stack.
Class: a blueprint that groups data and functions together. MinStack is a class. Each call such as MinStack() makes one stack with its own two lists.
Minimum: the smallest value in a set of values.
Running minimum: the smallest value among the items that are in the stack at a given moment.
Duplicate: a value that appears more than once.
O(1): work that takes the same amount of time however many items there are.

The problem with asking for the minimum

Start with a small example. Push 5, then 3, then 7, then 3, then 1. The stack now holds five values, with 1 on top. The smallest value is 1.

Pop the 1. The smallest value is now 3, because the 3 that was pushed fourth is still there. Pop the 3. The smallest value is still 3, because the second 3 is still in the stack. Pop again and the 7 leaves. Pop the second 3, and the smallest value is 5.

Each time the answer changes, the stack has to be searched again. A scan works, but it is slow when the stack is large and the question is asked often. The aim is to know the answer already, the moment the question is asked.

The idea: a second stack of running minimums

Keep two lists side by side.

values is the real stack. Pushes and pops go here.
mins holds the minimums. Its top is always the smallest value in values.

The rules are short.

To push x, append x to values. Then compare x with the last item of mins. If mins is empty, or x is less than or equal to its last item, append x to mins as well.
To pop, take the last item of values. Call it x. If x equals the last item of mins, pop mins as well.
To ask for the minimum, read the last item of mins. It is one step, so the answer takes O(1) time.

The second list is small in practice. It holds only values that were a new minimum when they were pushed, or that tie with the current minimum. A stack of 1000 numbers that are all distinct and in decreasing order keeps all 1000 in mins too. A stack of 1000 numbers that go up keeps only the first one.

Worked example 1: push and pop with a trace

Take the same five values, pushed in order: 5, 3, 7, 3, 1. Here is what each stack holds after each push. The lists go from bottom to top, so the last item in each list is the top.

Push	`values`	`mins`	Minimum
5	[5]	[5]	5
3	[5, 3]	[5, 3]	3
7	[5, 3, 7]	[5, 3]	3
3	[5, 3, 7, 3]	[5, 3, 3]	3
1	[5, 3, 7, 3, 1]	[5, 3, 3, 1]	1

Step 3 is the interesting one. The 7 is larger than the current minimum 3, so it is not copied to mins. Step 4 pushes a second 3. It equals the minimum, so it is copied too. That is why mins holds two 3s. The second copy is needed, as the next section shows.

The program that produces the output below is the class in the next section. It pushes these five values, prints both lists after each push, then pops everything and prints the state after each pop. The output came from a real run with Python 3.14.

Push 5, 3, 7, 3, 1 and pop everything:
  push 5  values [5]  mins [5]  min() = 5
  push 3  values [5, 3]  mins [5, 3]  min() = 3
  push 7  values [5, 3, 7]  mins [5, 3]  min() = 3
  push 3  values [5, 3, 7, 3]  mins [5, 3, 3]  min() = 3
  push 1  values [5, 3, 7, 3, 1]  mins [5, 3, 3, 1]  min() = 1
  pop 1  values [5, 3, 7, 3]  mins [5, 3, 3]  min() = 3
  pop 3  values [5, 3, 7]  mins [5, 3]  min() = 3
  pop 7  values [5, 3]  mins [5, 3]  min() = 3
  pop 3  values [5]  mins [5]  min() = 5
  pop 5  values []  mins []

Read the pop lines. Popping 1 removes the last item of mins too, so mins goes back to the state of step 4. Popping 3 (the second one) removes the last item of mins because the values are equal. Popping 7 changes nothing in mins, because 7 was never copied there. Each pop leaves the two lists in the state they had before the matching push.

The code

This is the whole file, including the main function that printed the output above. Both stacks are plain lists. A Python list prints from bottom to top, so no helper is needed to read it in order.

Python · editable

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []

def push(self, x):
        self.values.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)

def pop(self):
        if not self.values:
            raise IndexError("pop from an empty MinStack")
        x = self.values.pop()
        if x == self.mins[-1]:
            self.mins.pop()
        return x

def min(self):
        if not self.mins:
            raise IndexError("min of an empty MinStack")
        return self.mins[-1]

def main():
    s = MinStack()
    print("Push 5, 3, 7, 3, 1 and pop everything:")
    for x in [5, 3, 7, 3, 1]:
        s.push(x)
        print(f"  push {x}  values {s.values}  mins {s.mins}  min() = {s.min()}")
    while s.values:
        popped = s.pop()
        line = f"  pop {popped}  values {s.values}  mins {s.mins}"
        if s.values:
            line += f"  min() = {s.min()}"
        print(line)

if __name__ == "__main__":
    main()

Save the code as minstack.py and run it with python3 minstack.py.

Three details matter here.

The first is the comparison x <= self.mins[-1]. It uses <=, not <, so a value equal to the current minimum is copied too. The next section shows why.

The second is x == self.mins[-1] inside pop. Both sides are whole numbers, and == compares their values. So this check works for any whole number, including large ones. The mistakes section shows the one trap in this area, which is is instead of ==.

The third is that pop checks if not self.values: before it calls self.values.pop(). Calling pop() on an empty list raises IndexError: pop from empty list. The check raises an error with a message that names the stack, so the error is easier to read.

Why the second stack stays correct

The claim is simple to state. After every operation, the last item of mins is the smallest value in values. The reason is a rule about how stacks work.

Think of the state of mins at each depth of values. Depth 1 is the bottom item, depth 2 is the next, and so on. At depth d, the last item of mins should equal the smallest of the first d values of values. Call that number m(d).

Pushing x makes a new depth d with value x. If x is less than or equal to m(d - 1), then m(d) equals x, and the push copies x onto mins, so the top is x. If x is larger, then m(d) is still m(d - 1), nothing is copied, and the top of mins is unchanged. Both cases are right.

Popping goes back to depth d - 1. Two cases again. If the popped value was copied to mins when it was pushed, it is the value that made m(d), and it is on top of mins, so popping mins leaves the top at m(d - 1). If it was not copied, it was larger than m(d - 1), so the top of mins was already m(d - 1), and it stays that way.

This works because mins only changes at the top, in the reverse order of the pushes. When the stack is popped back to depth d - 1, mins looks exactly as it did when depth d - 1 was the top. The equal-to test in pop is what makes the first case work. Only the copy that belongs to the popped value is removed.

Worked example 2: duplicates, and the bug they cause

Duplicates are the hard case. Suppose you push 2 twice and then pop once.

The first 2 goes onto values, and mins is empty, so the 2 is copied. The second 2 goes onto values. It is less than or equal to the last item of mins, which is 2, so it is copied too. mins now holds [2, 2]. Pop one value. The popped 2 equals the last item of mins, so one copy is removed. mins holds [2], and the minimum is still 2, which is correct because one 2 is still in values.

The mins list goes from [2] to [2, 2] to [2] in those steps, and min() returns 2 at the end.

Now imagine a version that uses < instead of <=. This is a common first attempt, because "smaller" sounds like the right word. The file buggy_minstack.py below is that version. The only change is in push.

class BuggyMinStack:
    def __init__(self):
        self.values = []
        self.mins = []
 
    def push(self, x):
        self.values.append(x)
        if not self.mins or x < self.mins[-1]:  # strict: duplicates are not recorded
            self.mins.append(x)
 
    def pop(self):
        x = self.values.pop()
        if x == self.mins[-1]:
            self.mins.pop()
        return x
 
    def min(self):
        if not self.mins:
            raise IndexError("min of an empty BuggyMinStack")
        return self.mins[-1]
 
 
def main():
    s = BuggyMinStack()
    s.push(2)
    s.push(2)
    print("min after two pushes of 2:", s.min())
    s.pop()
    print("values left:", len(s.values))
    print("min after one pop:", s.min())
 
 
if __name__ == "__main__":
    main()

With <, the second 2 is not copied, so mins holds one 2. The pop of the top 2 sees that it equals the last item of mins, and removes that single copy. Now mins is empty, but one 2 is still in values. Here is the real output.

min after two pushes of 2: 2
values left: 1
Traceback (most recent call last):
  ...
IndexError: min of an empty BuggyMinStack

The lines between the first line and the last line are left out. They only show file names and line numbers on the machine that ran the program. The stack still holds a 2, yet the minimum is gone. The fix is the <= in the first version. The rule to remember is that every copy of a minimum needs its own entry in mins, so that each pop removes exactly one.

Worked example 3: the max stack

A max stack answers "what is the largest value now?" The method is the same with the comparison reversed. Keep a second list, called here maxs. Append x to maxs when maxs is empty or x is greater than or equal to its last item. Pop removes from maxs when the popped value equals its last item.

The version below also includes a check. It runs 2000 rounds of random pushes and pops against a plain list, which is easy to trust because it is simple. After every step, it compares max() with the largest value in the list. The random values are between 0 and 4, so duplicates happen often.

Python · editable

import random

class MaxStack:
    def __init__(self):
        self.values = []
        self.maxs = []

def push(self, x):
        self.values.append(x)
        if not self.maxs or x >= self.maxs[-1]:
            self.maxs.append(x)

def pop(self):
        if not self.values:
            raise IndexError("pop from an empty MaxStack")
        x = self.values.pop()
        if x == self.maxs[-1]:
            self.maxs.pop()
        return x

def max(self):
        if not self.maxs:
            raise IndexError("max of an empty MaxStack")
        return self.maxs[-1]

def main():
    rng = random.Random(7)
    checks = 0
    for _ in range(2000):
        s = MaxStack()
        model = []
        for _ in range(50):
            if not model or rng.randrange(3) != 0:
                x = rng.randrange(5)  # small range forces many duplicates
                s.push(x)
                model.append(x)
            else:
                expected = model.pop()
                got = s.pop()
                if expected != got:
                    raise AssertionError("pop mismatch")
            if model:
                if s.max() != max(model):
                    raise AssertionError("max mismatch")
                checks += 1
    print("max checks passed:", checks)

if __name__ == "__main__":
    main()

Run it and it prints:

max checks passed: 98037

The count is about 49 checks for each of the 2000 rounds, because a check runs after each step that leaves the list non-empty. The program printed no error, which means every check agreed with the plain list. The checks use raise AssertionError(...) instead of assert, because Python skips assert lines when it runs with the -O option. A test like this is a good habit for any stack with an extra rule, because a plain list is an easy reference to compare against.

Common mistakes

Using < where <= is needed. This is the bug in the buggy version above. The symptom is an IndexError from min() while the stack still has values. The cause is that duplicates were not recorded, so one pop removed the only entry in mins. Use <= for a min stack and >= for a max stack.

Popping mins on every pop. A tempting shortcut is to always pop mins as well. That breaks as soon as the popped value is larger than the minimum. Take a stack with 1 and then 5. The 5 was not copied to mins, so mins holds only the 1. A plain pop of mins now removes the 1. The stack still holds a 1, and min() raises an error. Only pop mins when the popped value equals its last item.

Comparing with is instead of ==. is checks whether two names point to the same object. == checks whether two values are equal. For whole numbers, is can give the wrong answer. This snippet creates two equal numbers at run time:

a = int("1000")
b = int("1000")
print("1000 == 1000:", a == b)
print("1000 is 1000:", a is b)

1000 == 1000: True
1000 is 1000: False

CPython, the standard Python implementation, keeps one shared object for each whole number from -5 to 256. So is looks right for small numbers, and the result for 256 is True while the result for 257 is False. Do not rely on this, because it depends on the Python version. Use == to compare values.

Reading the last item of an empty list. values[-1] on an empty list raises an error. Python does not return a default value. Here is the real message:

m = []
print(m[-1])

IndexError: list index out of range

The MinStack class avoids this by checking that the list is not empty first. Do the same in any code that reads mins[-1].

Forgetting that both stacks must agree. A push or pop that changes values but not mins gives a wrong answer later, not at once. The random test above is the kind of check that catches this. Test with many duplicates, because duplicates are where the rule is easy to break.

Practice

Exercise 1: trace a short sequence

Push 4, push 4, push 2, then pop once. Write the contents of values and mins after the pop, and the minimum.

Show the answer

After the three pushes, values is [4, 4, 2] and mins is [4, 4, 2]. The pop removes 2 from values, and 2 equals the last item of mins, so that is removed too. Now values is [4, 4] and mins is [4, 4]. The minimum is 4.

Exercise 2: trace with duplicates at the bottom

Push 3, push 1, push 1, push 2. Then pop, pop, pop. Give the minimum after each pop.

Show the answer

After the pushes, values is [3, 1, 1, 2] and mins is [3, 1, 1]. The first pop removes 2, which is not the minimum, so mins stays as it is. The minimum is 1. The second pop removes one of the 1s, which equals the last item of mins, so mins becomes [3, 1]. The minimum is 1. The third pop removes the other 1, so mins becomes [3]. The minimum is 3. The answers are 1, 1 and 3.

Exercise 3: the change for a max stack

Explain in one or two sentences why the max stack appends to maxs when x >= self.maxs[-1], and what would go wrong if it used >.

Show the answer

The max stack must keep a copy of every value that ties with the current maximum, for the same reason the min stack keeps every tie. With >, the second of two equal maximums is not copied, and popping the top one removes the only entry. The maximum is then lost while a copy is still in values.

Exercise 4: why the `is` comparison fails

Explain why int("1000") is int("1000") gives False, and give a fix.

Show the answer

Python creates two separate int objects for those two calls, because 1000 is outside the range of shared small integers. is compares the two objects, and they are different. The fix is ==, which compares the values. int("1000") == int("1000") gives True.

Exercise 5: one stack instead of two

A different design stores pairs in a single list. Each entry is a tuple, such as (x, smallest), that holds a value and the smallest value at or below it. Write the three operations in words, and say what this design costs compared with the two-list design.

Show the answer

Push x by appending the pair (x, the smaller of x and the smallest value in the pair below). If the list is empty, the smallest value is x itself. Pop removes the last pair. The minimum is the second item of the last pair. Each push and pop does one step, so the operations stay O(1). The cost is that every pair stores two values, even when most entries do not change the minimum. The two-list design stores only the extra copies, so it uses less memory when values rarely hit a new minimum, and the single-list design is simpler to read.

Summary

A min stack keeps a second list, mins, whose last item is always the smallest value in the real stack.
A push copies the value to mins only when it is less than or equal to the current minimum. A pop removes from mins only when the popped value equals its last item.
Using <= on push is what keeps duplicates. Each copy needs its own entry, so each pop removes exactly one.
A max stack uses the same method with >=.
Compare values with ==, not is, and check that the list is not empty before reading [-1].

Min stack and max stack in Python

Why it matters

Words you will need

The problem with asking for the minimum

The idea: a second stack of running minimums

Worked example 1: push and pop with a trace

The code

Why the second stack stays correct

Worked example 2: duplicates, and the bug they cause

Worked example 3: the max stack

Common mistakes

Practice

Exercise 1: trace a short sequence

Exercise 2: trace with duplicates at the bottom

Exercise 3: the change for a max stack

Exercise 4: why the is comparison fails

Exercise 5: one stack instead of two

Summary

Stuck? Ask the tutor

Exercise 4: why the `is` comparison fails