Where it runs
1. The problem
A plain stack puts a value on, takes it off and shows the top in O(1). But it has no fast answer to "what is the smallest value in here right now?". You would have to look through the whole stack, which is O(n) for every question. And the question comes up all the time: the lowest price in a trading session, the minimum in a history you can undo, the smallest item while data is added and removed.
A min stack (a stack with a minimum) answers getMin in O(1). The idea behind it is small, and it helps in many places: keep the ready answer next to the data, and don't compute it again.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Design problems where a stack must answer an extra question in O(1), such as its smallest value. Store the answer for each level next to the value, so a pop brings back the old answer.
The lesson task under the same name, with a second stack of running minimums.
Keep a second array beside the stack with a pending increment per level, and pass it down one level on each pop.
Keep one stack per frequency and the current top frequency, so pop reads the top of the highest stack.