Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Design state for constant-time answers: Minimum Stream.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Auxiliary stack design matches the clues
- 2Keep this true after every move: minima[i] is the minimum of values through index i
- 3Reach the result within O(n) build, O(1) query
Rules and pressure
- Target cost: O(n) build, O(1) query
- State rule: minima[i] is the minimum of values through index i
Lesson 1 of 3
Live algorithm trace
Auxiliary stack design
Complete execution1 of 6
0
5
push
1
2
2
4
3
1
The data structure starts empty with no finite minimum.
1
minimum = infinity2
for value in nums3
minimum = min(minimum, value)4
record minimumminimum = ∞minima = []
Truth to preserve / Cost target
Truth to preserve
minima[i] is the minimum of values through index i
Cost target
O(n) build, O(1) query
A designed data structure stores exactly the extra state future operations need. A minimum stack records the minimum after every push so queries never rescan history.
Your call · What should guide every step of this algorithm?