Rooftop Runner

MediumHeap / Priority Queue

Problem

A free-runner crosses a row of rooftops with heights heights, starting on rooftop 0 and always moving to the next one. Dropping down or moving to an equal height is free. Climbing from height h1 to a higher h2 requires either one ladder (any height) or exactly h2 - h1 bricks.

The runner carries bricks bricks and ladders ladders, and uses them optimally. Return the index of the farthest rooftop the runner can reach.

Example 1

Input:
heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1
Output:
4

Climbs on the way: 2→7 (5), 6→9 (3), 9→14 (5). Using the ladder on a 5-climb and 3 bricks on 6→9 reaches rooftop 4; the next climb of 5 needs 5 more bricks but only 2 are left.

Example 2

Input:
heights = [1, 5, 1, 5, 1], bricks = 3, ladders = 1
Output:
2

Example 3

Input:
heights = [3, 3, 3], bricks = 0, ladders = 0
Output:
2

Constraints

  • 1 ≤ heights.length ≤ 10^5
  • 1 ≤ heights[i] ≤ 10^6
  • 0 ≤ bricks ≤ 10^9
  • 0 ≤ ladders ≤ heights.length

Hint

Show the first hint

A ladder is worth the most when it replaces a big climb. Which climbs should get the ladders?

Walkthrough

How to approach it

01Clarify before coding

  • Do drops or flat moves cost anything? No.
  • Can resources be assigned after seeing the whole route? Yes, the runner uses them optimally, which is equivalent to deciding in hindsight.
  • What if every move is free? Return the last index.

02Brute force

For each target index, collect all climbs before it, sort them, give ladders to the largest and check if bricks cover the rest; return the last index that passes.

Cost: O(n² log n) time: re-sorting the climbs for each prefix. Binary search on the answer improves it to O(n log² n), still more than needed.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.