Previous and next smaller (both sides)

47 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Take the list 6, 0, 8, 2, 1, 5. A "ramp" is a pair of positions i < j with nums[i] ≤ nums[j], and its width is j − i. We want the widest ramp. Here the best is position 1 (value 0) to position 5 (value 5), width 4.

By hand you would check every pair: 15 pairs for 6 numbers, n(n − 1)/2 in general, which is 50 million pairs for ten thousand numbers. Most of those pairs are pointless. A left end at position 3 (value 2) can never beat a left end at position 1 (value 0): position 1 is further left and smaller, so any j that works for 3 works for 1 with a bigger width.

So the only left ends worth keeping are the ones that are smaller than everything before them. Here that is 6 (position 0) and 0 (position 1). Everything after 0 is bigger than 0, so it is a worse left end.

Build the structure, one piece at a time

Piece 1: a stack of candidate left ends. Walk left to right. Push a position only if its value is smaller than the value on top of the pile. The pile then holds positions with strictly decreasing values: 0(6), 1(0) in the example. The other four positions are never pushed.

Piece 2: scan right ends from the far right. Now walk j from the last position backwards. For each j, while the top of the pile has a value ≤ nums[j], that top is a valid left end for this j: record the width j − top and pop it.

Why pop? Because j is the rightmost right end we will ever try for that left end (we are moving leftwards), so no wider ramp with that left end can appear later.

The widest ramp recorded is 4. This two-pass trick, where the stack gives each element one boundary when pushed and the other when popped, is the general shape of the pattern: one pass can find both the previous smaller and the next smaller element of every position.

Why it is correct

The invariant has two halves. After pass 1 the pile holds every position that is a new minimum so far, in decreasing order of value. During pass 2, every position still on the pile has not yet found any right end, and every popped position was matched with the largest j that works for it.

For the first half: a position that is not a new minimum has an earlier, smaller position, which dominates it as a left end, so dropping it loses nothing. For the second half: when j pops the top i, every larger j′ > j was already tried and did not pop i, meaning nums[j′] < nums[i], so j is the furthest right end for i and j − i is the best width with left end i. Taking the maximum over all popped pairs gives the answer.

The same reasoning gives, for the "previous and next smaller" version: when j pops i, nothing between them was smaller than i (it would have popped i), so j is the next smaller, and the element below i on the pile is the previous smaller.

Why it is fast

Pass 1 touches each position once. In pass 2 each position on the pile is popped at most once, and j moves n steps.

work ≤ n (pass 1) + n (moves of j) + n (pops) = 3n, which is O(n)

For ten thousand numbers that is thirty thousand steps instead of fifty million pairs.

How to recognise it in an interview

The cues are "for each element, the nearest smaller (or greater) on both sides", "widest pair with a condition", or a sum where each element contributes according to how far it can extend left and right. Say: "A monotonic stack gives each element its left boundary at push time and its right boundary at pop time, so one pass finds both."

Maximum Width Ramp is the example above. Sum of Subarray Minimums uses the left and right boundaries to count how many subarrays each element is the minimum of, then multiplies. Shortest Unsorted Continuous Subarray uses the same stack to find the first and last position that is out of order.

02The idea in one line

One pass finds both neighbours: the popped element's right bound is the popper.

Reach for it when: Contribution sums, maximum width ramp, 132 pattern, visible counts.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Maximum Width Ramp on [6,0,8,2,1,5]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Pass 1: push only indices that are smaller than every earlier value
2. 6 is a new minimum: push index 0
3. 0 is a new minimum: push index 1
4. 8 ≥ 0: a worse left end, skip
5. 2 ≥ 0: a worse left end, skip
6. 1 ≥ 0: a worse left end, skip
7. 5 ≥ 0: a worse left end, skip
8. Pass 2: scan j from the right; pop while nums[top] ≤ nums[j]
9. nums[1]=0 ≤ nums[5]=5: ramp width 4
10. j=4: no left end ≤ 1 remains, move on
11. j=3: no left end ≤ 2 remains, move on
12. nums[0]=6 ≤ nums[2]=8: ramp width 2
13. Widest ramp: i=1 (0) to j=5 (5), width 4
14. Two linear passes, each index pushed and popped once: O(n)

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Monotonic Stack: Next greater element, Largest rectangle (bounds by pops), Greedy removal with a stack.