Where it runs
1. The problem
You have temperatures for 8 days: [73, 74, 75, 71, 69, 72, 76, 73]. For every day you want to know how many days you wait until it gets warmer. Day one is 73 and day two is 74, so the answer for day one is 1. Day three is 75, and it gets warmer only on day seven (76), so the answer is 4. If no warmer day ever comes, the answer is 0.
The first plan: from each day, walk forward until you find a warmer one. That works, and the answer is correct. But on a long list it is a loop inside a loop. On 10,000 days it comes to almost 50,000,000 comparisons (49,995,000 when the temperatures only go down). The same warm day gets looked at again by every day waiting before it.
You can answer for all days in one pass. Each day is then handled a fixed small number of times, however the temperatures go.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includednextGreater([2, 7, 3, 1, 5, 4, 8])For each number, find the first bigger number to its right. The stack holds the indices still waiting for an answer.
Bars: 40 readings that drift downward, where a bigger value is usually far away.
One operation is one comparison. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n²)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- next greater / next smaller element
- daily temperatures until it gets warmer
- largest rectangle in a histogram
- trap rainwater between bars
- span/streak that ends at the first bigger or smaller value
Looks similar, isn't
- Stack
A plain stack pops when you say so. A monotonic stack pops on a comparison.
- Monotonic deque
A deque also drops elements that fall out of a window. With no expiry by age, a stack is enough.
- Sliding window (variable)
A window answers questions about a range. This stack answers about one boundary element per index.
- Binary heap
A heap gives the global maximum in O(log n). The stack gives the nearest bigger neighbour in O(1).
- Sorting with a comparator
Sorting throws away positions. Next greater questions are entirely about position.
n up to 1e5 elements gives O(n). Each element is pushed once and popped at most once.
On LeetCode
Problems that ask, for every element, for the next or previous bigger or smaller one. A stack of still unanswered positions, kept in order, answers each of them once.
Run the lesson's next greater pass over nums2, store the answers in a map, and read them for nums1.
The lesson's opening example, where the answer is the distance between positions instead of the value.
The same stack looking backward, where each price pops every price on the stack not above it and absorbs their spans.
When a bar is popped, the bar that pops it and the new top are its first shorter neighbours on each side, which fixes the rectangle's width.