Find the next smaller with a stack
Updated
Same recipe, pop-while a[top] > a[j]. Next smaller of i is the first later strictly smaller value. Decreasing arrays find a next at every step. Increasing arrays find none.
What to focus on
Do not reuse a next-greater stack without flipping the test. Answers go into an array of the same length as a.
Worked examples
simple
a = [3, 4, 1]- 3→1, 4→1, 1 none
Result: [1, 1, none]
none
a = [1, 2, 3]- increasing
Result: [none, none, none]
each next
a = [3, 2, 1]- each pops previous
Result: [2, 1, none]
Try it
Write nextSmaller(a). a is an array of integers. Return an array of the same length. nextSmaller[i] is the first later strictly smaller value, or a sentinel. Pop while the top value is greater. Stack indices. a = [3, 4, 1] → [1, 1, none]. a = [1, 2, 3] → [none, none, none]. a = [3, 2, 1] → [2, 1, none].
a is a non-empty list of integers. Next smaller is strictly smaller. Leftovers get a sentinel, not an error.