Next Smaller Element
For each element, find the first smaller element to its right (−1 if none).
- 1 <= n <= 10⁵
- 1 <= nums[i] <= 10⁹
- Return -1 where no smaller element exists
Intuition
The next smaller element problem asks, for every element, for the first smaller element to its right. The brute force is easy to picture: for each index, walk rightward until something smaller appears. That is O(n²), and the reason it is wasteful is worth being precise about — the scans repeat each other. When index 5 walks right looking for its answer, it re-examines the exact elements index 4 just finished examining.
The fix comes from noticing what happens to elements that are still waiting for an answer. Suppose you scan left to right and keep a pile of indices whose answers are still unknown. When a new value x arrives, it settles the question for every waiting element larger than x at once, because x is to their right and smaller than them — and since you are scanning in order, it is the first such element each of them has seen.
That pile is a stack, and it has a property worth stating plainly:
- The values in the stack are always increasing from bottom to top.
That is not something you enforce with extra code; it falls out of the popping. Any element that would break the increasing order is exactly the element that just got popped, because it is larger than the incoming value. So each new value pops a run of larger waiters off the top, hands each of them its answer, and then joins the pile itself to wait its turn. Anything still waiting when the scan ends has nothing smaller to its right, and gets −1.
Identical machinery to next-greater with the comparison flipped, which also flips what the stack holds: values now sit in increasing order. Seeing that one operator controls the stack's whole invariant is the transferable part — it's how you'd derive previous-smaller or previous-greater on the spot.
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(n) space.
Understand what the stack is holding
The stack stores indices whose answer is not yet known, kept so their values increase from bottom to top. Storing indices rather than values matters: you need to know where to write each answer, and duplicate values would otherwise be indistinguishable. Initialise result to all −1 so the no-answer case needs no extra work later.
Scan left to right, one element at a time
Move through the array in order. The current element plays two roles on each iteration — first it answers older elements, then it becomes a waiter itself. Keeping those two roles separate in your head is what makes the code easy to write correctly.
Pop every waiter this element defeats
While the stack is non-empty and the value at its top index is greater than the current value, pop it and set result[popped] = current. This is a while loop, not an if — one small element can settle many waiters at once, which is why the array [5, 4, 3, 1] resolves three answers on its final step.
Push the current index and move on
After the popping stops, the current element has no answer yet, so push its index. The stack is still increasing: everything larger than it was just removed. This invariant is what guarantees you never need to search inside the stack.
Whatever remains gets −1
When the scan finishes, any index still on the stack was never popped, meaning no smaller value ever appeared to its right. Their result entries are already −1 from initialisation, so there is nothing to do here — the initial value did the work.
Why this is linear, not quadratic
Each index is pushed exactly once and popped at most once, so the total number of stack operations across the whole run is bounded by 2n. The inner while loop looks nested, but its total work is amortised across the outer loop, giving O(n) time and O(n) space in the worst case, when the array is strictly increasing and nothing ever pops.
The same skeleton solves the whole family
Next Greater Element is this code with the comparison flipped to <, which makes the stack decreasing instead. Previous Smaller Element is the same scan run right to left. Recognising the monotonic stack shape is more valuable than memorising any one of these four variants.
Solution & live demo
Common pitfalls
Flipping the comparison but expecting a decreasing stack
stack = [] # indices, values decreasing while stack and nums[stack[-1]] > x:
stack = [] # indices, values increasing while stack and nums[stack[-1]] > x:
The code is right; the mental model isn't. Popping everything larger than the newcomer leaves the stack increasing from bottom to top. Carrying over next-greater's "decreasing" assumption is what makes the follow-up variants go wrong.
Using >= and mis-answering equal values
while stack and nums[stack[-1]] >= x:
while stack and nums[stack[-1]] > x:
An equal element is not smaller, so resolving a pending index with it reports a wrong answer — on [2, 2] the first index would get 2 instead of -1. Strictness in the pop test must match strictness in the question.
Edge cases
No pops until the end — all −1? No: each element's right neighbours are larger, so yes, all −1.
Strictly-smaller wanted → equals stay on the stack.