Write answers when popping
Updated
The moment a[j] pops i, a[j] is the answer for i. Write answer[i] = a[j] (or j). Do not wait until the end to discover it. The end is only for leftovers.
What to focus on
If you pop several i's at one j, they all share that same next element j. Order of those pops is nearest-first (the top i is the closest index).
Worked examples
one j many i
a = [2, 1, 3], j=2- pops i=1 then i=0
- both answers 3
Result: answer[1]=3, answer[0]=3
no write on push
a = [3, 2, 1], each i only pushes- no pops
- no writes yet
Result: answers still sentinel
end leftovers
a = [3, 2, 1], after scan- stack [0,1,2]
- all none
Result: fill sentinel
Try it
Write writeOnPop(a). a is an array of integers. When a[j] pops i, write answer[i] = a[j] immediately. Leftovers get a sentinel at the end. a = [2, 1, 3], j=2 → answer[1]=3, answer[0]=3. a = [3, 2, 1], each i only pushes → answers still sentinel. a = [3, 2, 1], after scan → fill sentinel.
a is a non-empty list of integers. Answer is prefilled with a sentinel. Strictly greater.