The next one taller than this
A shelf-planning tool walks a row of stacked crates and, for each one, reports the height of the first crate to its right that stands taller.
- Look only to the right of each crate.
- Report the height of the first taller crate, not how far away it is.
- A crate with nothing taller to its right reports -1.
- Equal height is not taller.
next_taller(heights: list<int>) → list<int>
Where you start
def next_taller(heights: list[int]) -> list[int]:
Worked examples
| Call | Result |
|---|---|
next_taller([2, 1, 2, 4, 3]) | [4, 2, 4, -1, -1] |
next_taller([5, 4, 3]) | [-1, -1, -1] |
next_taller([1, 2, 3]) | [2, 3, -1] |
next_taller([2, 2, 2]) | [-1, -1, -1] |
Hint
Walk once, keeping a stack of the crates still waiting for an answer. Each new height settles every waiting crate shorter than it.
Reference solution in Python
def next_taller(heights: list[int]) -> list[int]:
answer = [-1] * len(heights)
waiting = []
for i, height in enumerate(heights):
while waiting and heights[waiting[-1]] < height:
answer[waiting.pop()] = height
waiting.append(i)
return answer