Store pairs on a stack
Updated
A stack item can be a pair (value, extra) — min so far, index, count, previous state. Push and pop the whole pair together so the extra stays aligned with the value.
What to focus on
Do not keep a parallel array that you forget to pop. One stack of pairs, one LIFO. Peek.value and peek.extra.
Worked examples
value and min
a = [(4,4), (1,1), (9,1)]- each item is (value, min-at-push)
Result: top extra is 1
value and index
a = [(2,0), (1,1)]- indices 0 and 1
Result: top is value 1 at i=1
after pop
a = [(4,4), (1,1), (9,1)], pop- remove (9,1)
- top extra still 1
Result: aligned
Try it
Write pushPair(a, value, extra). a is the stack of pairs. value and extra are integers popped together. Push (value, extra). Peek extra. Pop once and the extras stay aligned. Push (value, min) for 4 then 1 then 9. Peek extra is 1. Pop once and extras stay aligned.
The stack of pairs is non-empty. Each item is a (value, extra) pair popped together.