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.
nextTaller(heights: list<int>) → list<int>
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func nextTaller(heights []int) []int {
}Worked examples
| Call | Result |
|---|---|
nextTaller([]int{2, 1, 2, 4, 3}) | []int{4, 2, 4, -1, -1} |
nextTaller([]int{5, 4, 3}) | []int{-1, -1, -1} |
nextTaller([]int{1, 2, 3}) | []int{2, 3, -1} |
nextTaller([]int{2, 2, 2}) | []int{-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 Go
func nextTaller(heights []int) []int {
answer := make([]int, len(heights))
for i := range answer {
answer[i] = -1
}
waiting := []int{}
for i, height := range heights {
for len(waiting) > 0 && heights[waiting[len(waiting)-1]] < height {
answer[waiting[len(waiting)-1]] = height
waiting = waiting[:len(waiting)-1]
}
waiting = append(waiting, i)
}
return answer
}