Min stack and max stack

Why this matters

A stack has three basic actions. push adds a value on top, pop removes the top value, and top reads the top value without removing it. Some programs need a fourth question answered quickly: what is the smallest value in the stack right now? A stack of prices might need the lowest price so far. A stack of undo steps might need the smallest step. If you answer the question by looking at every item, the work grows with the size of the stack. Each question costs more as the stack grows.

A min stack is a stack that answers "what is the smallest value?" in one step, no matter how many items it holds. It does this by remembering a little extra work at each push. This lesson builds that idea from nothing, traces it by hand, and then adds the matching max stack. It also covers duplicates, the one case where a careless version gives a wrong answer.

The plain push and pop rules are covered in the module's first lesson, Stacks and balanced parentheses. This lesson only adds the minimum.

A small example to start

Push three numbers in this order: 5, 3, 7. The stack now holds 5 at the bottom, then 3, then 7 on top. The smallest value is 3.

Now pop. The 7 leaves, and the smallest value is still 3. Pop again. The 3 leaves, and the smallest value is now 5, the only value left.

The hard moment is the second pop. After it, the program has to know that 5 is the smallest value remaining. The 3 that just left was the old answer, so the program must not forget what was underneath it. A simple way to be sure is to scan the whole stack for the smallest value after every pop. That scan is slow for a large stack. The lesson's method avoids the scan.

The idea: a running minimum beside each entry

Keep two stacks side by side.

• The first stack, called values in the code below, holds the real values in push order.
• The second stack, called mins below, holds the running minimum. Entry i of mins is the smallest value among entries 0 through i of values.

When you push a value x, you push two things. You push x onto values. You push onto mins the smaller of x and the current top of mins. If mins is empty, the new value is the only value, so x itself goes on mins.

When you pop, you remove the top of both stacks. The answer to "what is the smallest value?" is the top of mins. Reading it takes one step, whatever the size of the stack.

Why does this stay correct after pops? Each entry of mins depends only on the values at or below it in values. Pops only remove from the top. So whenever an entry is still on the stack, everything under it is unchanged, and its running minimum is still correct. The stack never has to look back at values that were already removed.

Worked trace, step by step

Push 5, 3, 7, 3, 1, then pop twice. The table shows the two stacks after each step, bottom on the left and top on the right.

Look at the push of 7. The top of mins before it was 3, and 7 is larger than 3, so the new entry is 3. The 7 is on the stack, but its running minimum is still 3, because the 3 underneath is smaller. Now look at the push of 1. It is smaller than 3, so the new running minimum is 1. The top of mins shows that at a glance.

The code

The class below is the whole min stack. It uses std::vector as the storage for both stacks, because a vector grows at its back and can pop from its back in one step.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>
 
class MinStack {
public:
    void push(int value) {
        values_.push_back(value);
        mins_.push_back(mins_.empty() ? value : std::min(value, mins_.back()));
    }
 
    void pop() {
        require_not_empty();
        values_.pop_back();
        mins_.pop_back();
    }
 
    int top() const {
        require_not_empty();
        return values_.back();
    }
 
    int minimum() const {
        require_not_empty();
        return mins_.back();
    }
 
    bool empty() const { return values_.empty(); }
    std::size_t size() const { return values_.size(); }
 
private:
    void require_not_empty() const {
        if (values_.empty()) {
            throw std::out_of_range("MinStack is empty");
        }
    }
 
    std::vector<int> values_;
    std::vector<int> mins_;
};
 
int main() {
    std::cout << "MinStack trace\n";
    MinStack s;
    for (int x : {5, 3, 7, 3, 1}) {
        s.push(x);
        std::cout << "push " << x << ": top " << s.top() << ", min " << s.minimum() << '\n';
    }
    while (!s.empty()) {
        std::cout << "pop " << s.top() << ": min before pop " << s.minimum() << '\n';
        s.pop();
    }
}

The require_not_empty helper throws an error when someone asks for the top or the minimum of an empty stack. The Common mistakes section shows the message it prints. Without the check, the code would read past the end of a vector, which is undefined behaviour. In plain words, undefined behaviour means the program may print garbage, crash later, or appear to work. The check turns that hidden bug into a clear error at the point of the mistake.

Compile and run it with the flags used in this course:

g++ -std=c++20 -Wall -Wextra -o min_stack min_stack.cpp
./min_stack

The output is:

MinStack trace
push 5: top 5, min 5
push 3: top 3, min 3
push 7: top 7, min 3
push 3: top 3, min 3
push 1: top 1, min 1
pop 1: min before pop 1
pop 3: min before pop 3
pop 7: min before pop 3
pop 3: min before pop 3
pop 5: min before pop 5

The lines match the table. After the push of 1, the minimum is 1. After that pop, the minimum is 3, which is the value left at the top of mins. Every step costs the same amount of work, because each push and each pop touches only the top of each vector.

Note on the cost: a push or pop on a vector takes constant time on average. Reading minimum() is one lookup. So each operation is O(1), which means its cost does not grow with the stack size.

Duplicates

Duplicates are values that appear more than once. They are the case where a min stack is easy to get wrong.

The code above has no special case for duplicates, because it pushes a running minimum for every value, whether the value is new or not. Look at what happens with two 3s. Push 3, push 3, push 4, then pop once. The 4 leaves, and mins still has 3 on top, because mins has one entry for each value.

MinStack d;
d.push(3);
d.push(3);
d.push(4);
d.pop();
std::cout << "after pop, min " << d.minimum() << " (size " << d.size() << ")\n";
d.pop();
std::cout << "after pop, min " << d.minimum() << " (size " << d.size() << ")\n";

Output:

after pop, min 3 (size 2)
after pop, min 3 (size 1)

Both 3s are still counted, so the answer stays correct after the second pop too.

Saving space with a smaller mins stack

The version above stores one number in mins for every value. That is simple and uses about twice the memory. A common alternative stores less. It pushes a value onto mins only when the value is less than or equal to the current minimum, and it pops from mins only when the value leaving values matches the top of mins.

class CompactMinStack {
public:
    void push(int value) {
        values_.push_back(value);
        if (mins_.empty() || value <= mins_.back()) {
            mins_.push_back(value);
        }
    }
 
    void pop() {
        if (values_.empty()) {
            throw std::out_of_range("CompactMinStack is empty");
        }
        if (values_.back() == mins_.back()) {
            mins_.pop_back();
        }
        values_.pop_back();
    }
 
    int minimum() const { return mins_.back(); }
    std::size_t value_count() const { return values_.size(); }
    std::size_t min_count() const { return mins_.size(); }
 
private:
    std::vector<int> values_;
    std::vector<int> mins_;
};

The comparison in push must be <=, not <. The next section shows what goes wrong with <. With <=, a second copy of the current minimum is pushed onto mins, so each copy has its own entry. When one copy is popped, one entry leaves mins, and the other copy's entry is still there.

Here is the trace for pushes 3, 3, 1, 1, 2 followed by three pops.

CompactMinStack c;
for (int x : {3, 3, 1, 1, 2}) {
    c.push(x);
}
std::cout << "values " << c.value_count() << ", min entries " << c.min_count() << ", min " << c.minimum() << '\n';
for (int i = 0; i < 3; ++i) {
    c.pop();
}
std::cout << "after 3 pops: values " << c.value_count() << ", min entries " << c.min_count() << ", min " << c.minimum() << '\n';

Output:

values 5, min entries 4, min 1
after 3 pops: values 2, min entries 2, min 3

Before the pops there are five values and four min entries. The 2 was not pushed onto mins, because 2 is larger than the current minimum 1. After three pops, the values left are 3 and 3, and the minimum is 3. The two entries in mins are the two 3s, one for each value.

Both versions give the right answer. The full version is simpler to read. The compact version saves memory when the stack holds many values that are not minimums. A saving only matters when the stack is large, so start with the full version unless the memory use is a known problem.

Max stack

A max stack answers "what is the largest value?" The change is small. Replace std::min with std::max, rename mins_ to maxs_, and rename the function minimum to maximum. The push and pop logic stays the same.

class MaxStack {
public:
    void push(int value) {
        values_.push_back(value);
        maxs_.push_back(maxs_.empty() ? value : std::max(value, maxs_.back()));
    }
 
    void pop() {
        require_not_empty();
        values_.pop_back();
        maxs_.pop_back();
    }
 
    int top() const {
        require_not_empty();
        return values_.back();
    }
 
    int maximum() const {
        require_not_empty();
        return maxs_.back();
    }
 
    bool empty() const { return values_.empty(); }
 
private:
    void require_not_empty() const {
        if (values_.empty()) {
            throw std::out_of_range("MaxStack is empty");
        }
    }
 
    std::vector<int> values_;
    std::vector<int> maxs_;
};

Hand trace of pushes 2, 9, 4, 9 and two pops:

push 2: max 2
push 9: max 9
push 4: max 9
push 9: max 9
after two pops, max 9

The second 9 is popped first, and then the 4. The 9 at position 1 is still on the stack, so the maximum is still 9. If you need both the smallest and the largest at once, keep two separate running stacks, one for each answer, and push to both at the same time.

Worked examples

Example 1: the basic trace

Take the pushes 5, 3, 7, 3, 1 from earlier. You can check each answer by reading the table, which is the same process the code follows. The point to notice is that each push looks at one value only: the top of mins. A push never has to scan the stack.

Example 2: duplicates and the wrong comparison

Take the same pushes, but use the compact version with < instead of <=. The program below is the compact class with that one change, and without the empty check to keep it short. It pushes 3 and 3, then pops once.

class BuggyCompactMinStack {
public:
    void push(int value) {
        values_.push_back(value);
        if (mins_.empty() || value < mins_.back()) {
            mins_.push_back(value);
        }
    }
 
    void pop() {
        if (values_.back() == mins_.back()) {
            mins_.pop_back();
        }
        values_.pop_back();
    }
 
    std::size_t value_count() const { return values_.size(); }
    std::size_t min_count() const { return mins_.size(); }
 
private:
    std::vector<int> values_;
    std::vector<int> mins_;
};
 
// in main():
BuggyCompactMinStack b;
b.push(3);
b.push(3);
b.pop();
std::cout << "values " << b.value_count() << ", min entries " << b.min_count() << '\n';

Output:

values 1, min entries 0

Work through it. The first 3 goes onto mins, because mins is empty. The second 3 is not less than 3, so it is not pushed. There is one min entry for two values. When the pop removes the second 3, it is equal to the top of mins, so the code removes that entry. Now one value (the first 3) is left, but mins is empty. The next call to minimum() would read from an empty vector, which is undefined behaviour. The fix is to use <= in push.

Example 3: a list of commands

This example uses the full MinStack class from earlier. It runs a list of commands and prints the smallest value after each one. Commands are written as text, the way a log file or a user's undo history might record them. The std::stoi function turns the text "8" into the number 8.

const std::vector<std::string> steps = {
    "push 8", "push 5", "push 5", "push 9", "pop",
    "pop", "pop", "push 2", "pop"};
MinStack s;
for (const std::string& step : steps) {
    if (step == "pop") {
        s.pop();
    } else {
        s.push(std::stoi(step.substr(5)));
    }
    std::cout << step << " -> ";
    if (s.empty()) {
        std::cout << "stack is empty\n";
    } else {
        std::cout << "min " << s.minimum() << ", top " << s.top() << '\n';
    }
}

Output:

push 8 -> min 8, top 8
push 5 -> min 5, top 5
push 5 -> min 5, top 5
push 9 -> min 5, top 9
pop -> min 5, top 5
pop -> min 5, top 5
pop -> min 8, top 8
push 2 -> min 2, top 2
pop -> min 8, top 8

The fifth step, a pop, removes the 9, and the minimum is still 5 because the 5s are below it. The two pops after it remove the 5s, so the minimum returns to 8 only after the second 5 is gone. The push 2 makes 2 the minimum, and the last pop removes it, so the 8 becomes the minimum again. The stack never scanned its contents. Each answer came from the top of mins.

Common mistakes

Forgetting to pop the minimum stack

If pop removes from values_ but not from mins_, the two stacks drift apart. The minimum then comes from an old entry. A quick check is to compare the sizes after each pop: both stacks should have the same size in the full version. In the compact version, the sizes are allowed to differ, but a pop must still remove an entry from mins_ at the right moment.

Using < instead of <= in the compact version

This is the duplicate mistake shown in Example 2. The output values 1, min entries 0 is the sign of it: the min count should not reach zero while values remain.

Calling minimum() on an empty stack

An empty stack has no smallest value, so the call is an error. The class above throws an exception with a clear message. If you remove the check, the program may crash or print junk. Here is the real output of a program that makes the call on an empty MinStack:

terminate called after throwing an instance of 'std::out_of_range'
  what():  MinStack is empty

The first line names the exception type, and what() gives the message written in the class. Read the second line to find which stack was empty.

Comparing an int with a size

The size of a vector has type std::size_t, which is unsigned. Comparing it with an int produces a warning. This comes from the -Wall flag, which the course uses for every compile.

int sum_first(const std::vector<int>& items, int count) {
    int total = 0;
    for (int i = 0; i < items.size() && i < count; ++i) {
        total += items[i];
    }
    return total;
}

Compiler output (the file name and line number depend on your file):

mistakes.cpp: In function ‘int sum_first(const std::vector<int>&, int)’:
mistakes.cpp:31:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   31 |     for (int i = 0; i < items.size() && i < count; ++i) {
      |                     ~~^~~~~~~~~~~~

Fix it by making i a std::size_t, or by comparing with static_cast<int>(items.size()). The min stack classes in this lesson do not compare sizes with int, so they compile without this warning.

Pushing a value of the wrong type

The stack holds int values. Pushing text into it fails at compile time, which is the easiest kind of mistake to fix. The same rule applies to a plain std::vector<int>. For example, v.push_back("hi") produces this first error line from g++ 15 (the file name, line and column depend on your code):

typo.cpp:5:16: error: no matching function for call to ‘push_back(const char [3])’

Read the names in quotes. They show the function you called and the argument type that was wrong.

Practice

Exercise 1

Start with an empty MinStack. Run these steps in order: push 4, push 1, push 4, pop, pop. After each step, what is the minimum? Use the table method from this lesson.

Show the answer

After push 4 the minimum is 4. After push 1 it is 1. After push 4 it is still 1, because the 1 is below. After the first pop (removing the 4 on top) it is still 1. After the second pop (removing the 1) it is 4, the only value left.

Exercise 2

Why does the compact version need the value on top of values_ to equal the top of mins_ before it pops mins_? What goes wrong if you pop mins_ every time?

Show the answer

mins_ has an entry only for some values, not for every value. If you pop mins_ on every pop, you remove entries that belong to other values. For example, with pushes 5, 3, 7 the compact version has mins 5 and 3. Popping 7 must leave the 3 in mins_. An unconditional pop would remove the 3, and the minimum would wrongly become 5.

Exercise 3

Write a min stack that uses only one stack of pairs. Each entry stores the value and the running minimum. Push 6, push 2, push 8, and print the minimum. Then pop once and print the minimum, then pop again and print the minimum.

Show the answer

#include <algorithm>
#include <iostream>
#include <vector>
 
struct Entry {
    int value;
    int minimum;
};
 
class OneStackMin {
public:
    void push(int value) {
        int lowest = items_.empty() ? value : std::min(value, items_.back().minimum);
        items_.push_back({value, lowest});
    }
    void pop() { items_.pop_back(); }
    int minimum() const { return items_.back().minimum; }
 
private:
    std::vector<Entry> items_;
};
 
int main() {
    OneStackMin s;
    s.push(6);
    s.push(2);
    s.push(8);
    std::cout << s.minimum() << '\n';
    s.pop();
    std::cout << s.minimum() << '\n';
    s.pop();
    std::cout << s.minimum() << '\n';
}

Output, from running it:

2
2
6

The first minimum() call prints 2 because the stack holds 6, 2, 8 and 2 is smallest. After one pop the 8 is gone, and the 2 is still there. After a second pop the 2 is gone, and only the 6 remains. This version is the same idea as the two-stack version, with the pair stored together, so one pop removes both pieces at once.

Exercise 4

A CompactMinStack receives the pushes 4, 2, 2, 5, then one pop, then one more pop. How many entries are in mins_ after each step, and what is the minimum at the end?

Show the answer

After the pushes: values_ is 4, 2, 2, 5. mins_ gets 4 (first value), 2 (smaller), 2 (equal, so pushed), and then 5 is not pushed. So mins_ has 3 entries: 4, 2, 2.

After the first pop (removes 5): 5 is not equal to the top of mins_ (which is 2), so mins_ is unchanged with 3 entries.

After the second pop (removes 2 from values_): this 2 equals the top of mins_, so mins_ loses one entry and has 2 entries: 4, 2. The minimum is 2.

Exercise 5

Explain in your own words why the running minimum stored at position i never needs to change after the push. Use one example.

Show the answer

The running minimum at position i is the smallest value from position 0 through i. A later push adds a new position above i and does not change what lies at or below i. A pop removes only the top position. So while position i exists, every value under it is the same as when it was pushed. For example, with pushes 5, 3, 7, the entry for 3 is 3, and it stays 3 while the 7 is pushed above it. The entry for 7 is 3 too, because the 3 below is smaller.

Summary

• A min stack keeps a second stack of running minimums, one entry for each value in the main stack.
• Each push stores the smaller of the new value and the current minimum, so the top of the second stack is always the answer.
• Pops remove from the top of both stacks. The running minimums below stay correct, so no scanning is needed.
• Every operation takes constant time, so the cost does not grow with the stack size.
• Duplicates are safe with the full version. The compact version needs <= on push, or a second copy of the minimum is lost.
• A max stack works the same way with the larger value. A class that needs both answers can keep two running stacks.