Stacks and Monotonic Structures
Precomputing the answer at push time
If a query must be constant time, the answer has to already be sitting there when it is asked.
Key idea
The design constraint
Some problems do not ask you to compute anything clever. They ask you to build a structure where certain operations are guaranteed constant time, and the difficulty is entirely in the word guaranteed.
The move is almost always the same: if a query must be O(1), it cannot do any work, so the answer has to be computed when the data changes and stored somewhere it can simply be read.
A stack that knows its own total
Suppose a stack must support total() in constant time. Summing on demand is O(n). Keeping one running total alongside the stack works for push, and breaks on pop unless you can undo the addition, which here you can.
The more general fix, and the one that survives operations you cannot undo, is to store the answer as of that moment with each entry.
Why it works
Why popping needs no work
Each entry carries the answer for the stack that existed when it was pushed. Removing the top exposes the entry below, whose stored answer already describes exactly the stack that now remains.
That is the whole trick, and it is worth stating as an invariant: entry i holds the answer for the first i + 1 elements. Popping does not recompute anything because the answer for the shorter stack was recorded when the shorter stack was current.
Tip
It works for any aggregate you can extend
This works whenever the answer for a stack can be computed from the answer for the stack below it plus the new element. Sums qualify. So do minimums, maximums, counts, and products.
It does not work for aggregates that need the whole collection, such as a median, because those cannot be extended by one element in constant time. Recognizing which side of that line a query falls on tells you immediately whether this technique applies.
Cost
The cost
Every operation is O(1) and the space is O(n), doubled by the extra field. Storing one value per entry rather than a whole recomputation is what buys the constant time.
An alternative keeps a second stack that only records a new entry when the answer actually changes, which saves space on inputs where it rarely does and complicates the pop logic. Mention it as a refinement; the simple version is the one to write first.
Apply it to a different query
The problem below asks for exactly this design with a different aggregate. Decide what each entry needs to carry so that the required query reads a single stored value, and check that your rule still holds after a pop.
Which query can be made constant time this way?
You are storing an extra field with each stack entry so a query can read it directly. Which of these queries cannot be supported this way?
Min Stack
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.