Next Smaller Element
For each element, find the first smaller element to its right (−1 if none).
Open on GeeksforGeeks ↗02
Intuition
Next Greater with the comparison flipped: keep an increasing stack of waiters; each new element pops — answers — every waiter larger than it.
03
Approach
1
Mirror the monotonic stack
Stack holds indices with increasing values. New value x pops all waiters > x; x is their next smaller.
2
Drain leftovers as −1
Anything still waiting at the end has no smaller element to its right.
3
Same amortized bound
Push+pop once per index → O(n).
04
Solution & live demo
python
▶1def next_smaller(nums):
▶2 res = [-1] * len(nums)
▶3 stack = [] # indices, values increasing
▶4 for i, x in enumerate(nums):
▶5 while stack and nums[stack[-1]] > x:
▶6 res[stack.pop()] = x
▶7 stack.append(i)
▶8 return res
05
Edge cases
Increasing array
No pops until the end — all −1? No: each element's right neighbours are larger, so yes, all −1.
Equal neighbours
Strictly-smaller wanted → equals stay on the stack.
06
Complexity
Time
O(n)
Space
O(n)
Monotonic stack, one pass.