0811HardArrayDynamic ProgrammingSorting

Longest Descent Run

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A climbing wall has a row of ledges. height[i] is the height of the ledge at position i, and a climber can hop between ledges along the row.

Standing on ledge i, the climber may hop to ledge j when all three hold:

j is a different position with |i - j| <= reach;
height[j] < height[i], so every hop goes strictly downwards;
every ledge strictly between i and j is also lower than height[i], so nothing on the way blocks the hop.

The climber picks any ledge to start on and then hops as many times as they like, possibly not at all. Return the largest number of ledges a single run can touch, counting the ledge it starts on.

Examples

Example 1

Input: height = [10, 1, 9], reach = 2
Output: 3

Starting on the ledge of height 10, the climber hops two places right to the ledge of height 9, since 9 is lower than 10 and the ledge of height 1 in between is lower too, and then hops back one place left to the ledge of height 1. That run touches three ledges.

Example 2

Input: height = [4, 4, 4, 4], reach = 2
Output: 1

No hop is legal, because no ledge is strictly lower than another. A run therefore touches only the ledge it starts on.

Example 3

Input: height = [5, 5, 5, 1, 5, 5, 5], reach = 3
Output: 2

Starting on the ledge at position 2, the climber hops one place right onto the ledge of height 1. That run touches two ledges.

Constraints

1 <= height.length <= 1000
1 <= height[i] <= 10^5
1 <= reach <= height.length

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def longest_descent_run(height: list[int], reach: int) -> int:

Java

public int longestDescentRun(int[] height, int reach)

The intended approach

Time O(n log n + n * reach) for n ledges.Space O(n) for the height order and the per-ledge totals.

Every hop lands strictly lower, so handling the ledges from the lowest height upwards means each ledge's landing spots are already settled when its own total is computed. For a ledge, walk outwards to the right and then to the left, stopping at the first ledge that is not strictly lower, which is exactly the blocking rule; the ledge's total is one more than the best total among the spots the walks accept. The answer is the largest total over all ledges. The loop is iterative, so a thousand ledges cost no stack.

Pythonentry point: longest_descent_run

def longest_descent_run(height, reach):
    # A hop always lands on a strictly lower ledge, so if the ledges are handled
    # from lowest to highest, every landing spot a ledge can use has already been
    # finished. Walking outwards from a ledge and stopping at the first ledge
    # that is not lower enforces the rule that nothing in between may stand as
    # high as the ledge being left.
    #
    # Time: O(n log n) to order the ledges plus O(n * reach) for the two walks.
    # Space: O(n) for the order and the per-ledge totals.
    n = len(height)
    runs = [1] * n
    for i in sorted(range(n), key=lambda k: height[k]):
        h = height[i]
        best = 0
        limit = i + reach
        if limit > n - 1:
            limit = n - 1
        for j in range(i + 1, limit + 1):
            if height[j] >= h:
                break
            if runs[j] > best:
                best = runs[j]
        limit = i - reach
        if limit < 0:
            limit = 0
        for j in range(i - 1, limit - 1, -1):
            if height[j] >= h:
                break
            if runs[j] > best:
                best = runs[j]
        runs[i] = best + 1
    return max(runs)

The obvious version

Test every ordered pair of positions against the hop rule to build the move graph outright, then repeatedly relax the best chain length out of each position until a full sweep changes nothing. Every hop goes strictly downhill so the graph has no cycle and the sweeps settle; the answer is the largest chain length.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_longest_descent_run(height, reach):
    """Build the move graph outright, then relax the longest chain until stable."""
    n = len(height)
    moves = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j or abs(i - j) > reach:
                continue
            lo, hi = (i, j) if i < j else (j, i)
            blocked = False
            for k in range(lo, hi + 1):
                if k != i and height[k] >= height[i]:
                    blocked = True
                    break
            if not blocked:
                moves[i].append(j)
    total = [1] * n
    for _ in range(n):
        changed = False
        for i in range(n):
            for j in moves[i]:
                if total[j] + 1 > total[i]:
                    total[i] = total[j] + 1
                    changed = True
        if not changed:
            break
    return max(total)

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in