Iteration

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: