Problems › TypeScript › patterns
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>
Where you start
function nextTaller(heights: number[]): number[] {
}Worked examples
| Call | Result |
|---|---|
nextTaller([2,1,2,4,3]) | [4,2,4,-1,-1] |
nextTaller([5,4,3]) | [-1,-1,-1] |
nextTaller([1,2,3]) | [2,3,-1] |
nextTaller([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 TypeScript
function nextTaller(heights: number[]): number[] {
const answer: number[] = new Array(heights.length).fill(-1);
const waiting: number[] = [];
for (let i = 0; i < heights.length; i += 1) {
while (waiting.length > 0 && heights[waiting[waiting.length - 1]] < heights[i]) {
answer[waiting.pop() as number] = heights[i];
}
waiting.push(i);
}
return answer;
}