Step 8 of 8

Challenge: a MinStack<T>

Time for a classic interview problem, made generic. A normal stack gives you push, pop and top in O(1). Finding the minimum would normally mean scanning every element, O(n). The trick to make it O(1) is to remember the answer as you go.

Here's the same idea for a running maximum in a history of scores:

#include <algorithm>
#include <iostream>
#include <vector>

class ScoreLog {
public:
    void add(int s) {
        int best = best_.empty() ? s : std::max(s, best_.back());
        scores_.push_back(s);
        best_.push_back(best);          // the max of everything up to here
    }
    void undo() { scores_.pop_back(); best_.pop_back(); }
    int best() const { return best_.back(); }

private:
    std::vector<int> scores_;
    std::vector<int> best_;
};

int main() {
    ScoreLog log;
    for (int s : {40, 75, 60, 90}) {
        log.add(s);
        std::cout << "after " << s << ": best " << log.best() << "\n";
    }
    log.undo();
    std::cout << "after undo: best " << log.best() << "\n";
}

after 40: best 40
after 75: best 75
after 60: best 75
after 90: best 90
after undo: best 75

Why it works

At every position, best_ stores the maximum of all the values at or below that position. Since a stack only ever removes from the top, the values below never change. So after popping, the new top of best_ is still correct. Every operation is O(1).

Making it generic

For your MinStack<T>, apply the same idea with std::min, and use T everywhere a value appears. Two common designs:

• Store pairs {value, min_so_far} in one std::vector<std::pair<T, T>>.
• Keep two vectors, as ScoreLog does.

top() and min() return const T&, a reference to the stored element, so nothing is copied.

Your turn: write template <typename T> class MinStack where every operation is O(1), including finding the minimum:

• void push(const T& v)
• void pop() (assume non-empty)
• const T& top() const
• const T& min() const: the smallest element currently in the stack
• bool empty() const

Hint for the O(1) min: alongside each value, remember what the minimum was at that point. Or keep a second stack of minimums.

Previous: Template specialization