Furthest Building with Bricks and Ladders
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A parkour runner crosses buildings in a row from left to right, starting on the roof of building 0. Building i has height
heights[i]. Going from building i to i+1:
- if the next building is not higher, just go;
- if it is higher, either stack
heights[i+1] - heights[i]bricks or use one ladder.
You have bricks bricks and ladders ladders, and neither can be reused. Using them optimally, return the index of the furthest
building you can reach.
Examples
| heights | bricks | ladders | result |
|---|---|---|---|
[4, 2, 7, 6, 9, 14, 12] | 5 | 1 | 4 |
[4, 12, 2, 7, 3, 18, 20, 3, 19] | 10 | 2 | 7 |
[14, 3, 19, 3] | 17 | 0 | 3 |
Example 1 — Bricks for 2 → 7 (5), the ladder for 6 → 9; then 9 → 14 needs 5 more and nothing is left.
Example 2 — Ladders for 4 → 12 and 3 → 18, bricks for 2 → 7 (5) and 18 → 20 (2); 3 → 19 needs 16 bricks but only 3 remain.
Example 3 — 16 bricks cover 3 → 19.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(heights: int[], bricks: int, ladders: int) → int
Constraints
-
heights.length -
heights[i] -
bricks -
ladders
Expected complexity
- Time
- O(N log N)
- Space
- O(N)
Examples
| heights | bricks | ladders | Expected |
|---|---|---|---|
[4,2,7,6,9,14,12] | 5 | 1 | 4 |
[4,12,2,7,3,18,20,3,19] | 10 | 2 | 7 |
[14,3,19,3] | 17 | 0 | 3 |
Hint
Hint
Up to any point, the best plan uses ladders on the ladders largest climbs and bricks on the rest. Re-sorting the climbs for every
prefix is . Instead keep the laddered climbs in a min-heap: push each climb; when the heap exceeds ladders,
pop the smallest climb and pay for it with bricks; once bricks run out, the previous building is the answer. .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1128 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |