Waiting for a Bigger Wave
A surf school gets an hourly forecast of wave heights, in centimetres, for the day ahead. Students who arrive at a given hour always ask the same thing: if I paddle out now, how long until a wave bigger than this one comes in?
The school wants the answer for every hour of the forecast, printed on the board each morning.
Your task
Write hoursUntilBigger(heights). heights[i] is the forecast wave height in hour i. Return a list wait of the same length, where wait[i] is the number of hours from hour i until the first later hour with a strictly taller wave. If no later hour has a taller wave, wait[i] is 0.
An empty forecast gives an empty list.
hoursUntilBigger(heights: int[]) → int[]
Examples
heights = [5, 3, 4, 8, 6, 7]
[3, 1, 1, 0, 1, 0]
Hour 0 (5 cm) waits until hour 3 (8 cm): 3 hours. Hour 1 (3 cm) only waits 1 hour for the 4 cm wave. Hour 2 (4 cm) waits 1 hour for 8. Nothing after hour 3 beats 8, so it gets 0. Hour 4 (6 cm) waits 1 hour for 7. The last hour has nothing after it: 0.
heights = [4, 4, 2, 4]
[0, 0, 1, 0]
A 4 cm wave is not bigger than another 4 cm wave. Only hour 2 (2 cm) sees a taller wave, 1 hour later.
Constraints
- 0 ≤ heights.length ≤ 100,000
- 1 ≤ heights[i] ≤ 1,000
Start with brute force
For each hour, scan forward until you find a taller wave. That is two nested loops.
When the forecast is mostly falling, each scan runs to the end, so the total is about n² / 2 steps. With 100,000 hours that is around 5 billion steps. The waste: the same small waves are scanned again and again by every hour that comes before them.
Hints
0 of 4 shown- Hint 1
In
[5, 3, 4, 8], when you reach the 8, which earlier hours get their answer at that moment? - Hint 2
When a tall wave arrives, it answers every earlier hour that is still waiting and is smaller than it. So the hours still waiting, from oldest to newest, never get taller: if a newer one were taller than an older one, it would already have answered it.
- Hint 3
Keep the hours that are still waiting on a stack, newest on top. A new wave only has to look at the top: if it is taller than the top, it answers it and checks the next one; if not, it stops, because everything below is at least as tall.
- Hint 4
Walk the hours left to right with a stack of indexes. For each hour
i: while the stack is not empty andheights[top] < heights[i], poptopand setwait[top] = i - top. Then pushi. Anything left on the stack at the end keeps 0.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Turn the question around. Instead of each hour looking forward for its answer, let each new wave look back and answer every earlier hour it beats. The hours still waiting sit on a stack, and their heights never increase from bottom to top, so a new wave only needs to check the top.
Trace [5, 3, 4, 8, 6, 7] (the stack shows indexes, with heights in brackets):
- Hour 0 (5). Nothing waiting. Push. Stack: 0(5).
- Hour 1 (3). 3 is not taller than 5. Push. Stack: 0(5), 1(3).
- Hour 2 (4). 4 > 3: pop 1, wait[1] = 2 - 1 = 1. 4 is not taller than 5, stop. Push. Stack: 0(5), 2(4).
- Hour 3 (8). Pop 2, wait[2] = 1. Pop 0, wait[0] = 3. Push. Stack: 3(8).
- Hour 4 (6). Not taller than 8. Push. Stack: 3(8), 4(6).
- Hour 5 (7). Pop 4, wait[4] = 1. 7 is not taller than 8. Push. Stack: 3(8), 5(7).
Hours 3 and 5 are never answered and keep 0. Result: [3, 1, 1, 0, 1, 0]. Use <, not <=, in the loop: an equal wave is not bigger, so it must not answer the hour on top.
function hoursUntilBigger(heights) {
const wait = new Array(heights.length).fill(0);
const waiting = []; // indexes still waiting; their heights never increase upward
for (let i = 0; i < heights.length; i++) {
// the new wave answers every smaller wave still waiting
while (waiting.length > 0 && heights[waiting[waiting.length - 1]] < heights[i]) {
const j = waiting.pop();
wait[j] = i - j;
}
waiting.push(i);
}
return wait; // hours left on the stack keep 0
}def hours_until_bigger(heights):
wait = [0] * len(heights)
waiting = [] # indexes still waiting; their heights never increase upward
for i, h in enumerate(heights):
# the new wave answers every smaller wave still waiting
while waiting and heights[waiting[-1]] < h:
j = waiting.pop()
wait[j] = i - j
waiting.append(i)
return wait # hours left on the stack keep 0Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.