Iteration

Number of Steps Until a Higher Step

You're given an Array height which represents the heights of steps in a staircase. Return an Array where each entry contains the number of steps you need to walk in order to get to a higher step. If there's no such step, return infinity.

Example:

\notag \texttt{height = [10,5,3,7,5,3]} \\[2bp] \texttt{=> returns [inf,2,1,inf,inf,inf] }

Explanation: The first, 3rd, 4th, and 5th step don't have a higher step after them, so we give infinity for them. The 2nd step needs to walk 2 steps and the 3rd step needs to walk 1 step in order to get to a higher step.

First Few Test Cases:

You can solve this problem with brute-force, but this is slow and takes O(n $^2$ ) time. Instead, you should look for a solution that takes just a single pass over the array.

To do a single pass, we need to remember the steps that we've visited so we can update them if we ever reach a higher stair. We'll store each step in an array called pending, to indicate that the steps need to be updated.

When we take a new step, we should check whether the current step is taller than any of the pending steps. If it is, then we can update those stairs accordingly.

Now we're ready to code this up. Amazingly, all the stairs in the pending array are always sorted by decreasing height. This is because steps stop pending when the height increases. This lets us efficiently figure out which steps we should update - we can repeatedly pop the rightmost entry in the pending array to get all the stairs that we should update (the lowest steps).

Here's how you code this up:

Time Complexity $O(n)$ . Each step gets added and removed from the pending array.

Space Complexity $O(n)$ . The pending array can grow to size $n$ .

Mark as Completed:

Submits:

numStepsUntilHigherStep

Test your code to get an output here!

numStepsUntilHigherStep(

)

Test your code to get an output here!