Abstract / Summary

You want to reach the farthest building using bricks and ladders while minimizing the number of ladders used.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 51% (500k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “furthest building” problem: given a sequence of building heights, a limited number of bricks, and a limited number of ladders, determine the farthest index that can be reached by climbing upward steps. The algorithm adopts a greedy strategy that dynamically decides whether to allocate bricks or ladders to each upward climb, ensuring that ladders are reserved for the largest height differences while bricks cover the smaller ones.

Key Steps

The function begins by initializing an empty min-heap, named small, which will store the positive height differences encountered while iterating through the heights list.

small = []

A loop iterates from the second building to the last, computing the climb required to move from the previous building to the current one.

for i in range(1, len(heights)):
    climb = heights[i] - heights[i - 1]

If the computed climb is non-positive, the algorithm proceeds to the next iteration because descending or level movement does not consume resources.

if climb <= 0:
    continue

For a positive climb, the value is pushed onto the min-heap. This heap always contains the set of climbs that have been considered for ladder usage.

heappush(small, climb)

The algorithm then checks whether the number of climbs stored in the heap exceeds the available ladders. When this condition holds, the smallest climb in the heap is removed and covered with bricks, thereby preserving ladders for larger climbs.

if len(small) > ladders:
    if bricks < small[0]:
        return i - 1
    bricks -= heappop(small)

If at any point the remaining bricks are insufficient to cover the smallest climb in the heap, the function returns the index of the last reachable building, which is i - 1. Otherwise, after processing all buildings, the function returns the index of the final building.

return len(heights) - 1

Edge Cases Handled

The algorithm gracefully handles scenarios where no upward movement is required. When consecutive heights are equal or decreasing, the climb value is non-positive, triggering the continue statement and leaving both bricks and ladders untouched. This ensures that the function does not mistakenly consume resources on downhill steps.

When the number of ladders is zero, the condition len(small) > ladders becomes true for every positive climb. Consequently, each climb is immediately evaluated against the available bricks, and the function returns the correct furthest index once bricks are exhausted.

If the total number of positive climbs never exceeds the ladder count, the heap never triggers a brick deduction. In this situation, the function will successfully traverse the entire list and return the last index, demonstrating correct handling of abundant ladder resources.

The early exit condition if bricks < small[0] captures the exact moment when the remaining bricks cannot satisfy the smallest pending climb, guaranteeing that the function stops precisely at the last feasible building.

Performance Optimizations

The core optimization lies in the use of a min-heap to maintain the smallest climbs encountered so far. By pushing each positive climb onto the heap and only extracting the minimum when the heap size surpasses the ladder count, the algorithm ensures that bricks are always allocated to the least costly climbs. This selective extraction avoids unnecessary brick consumption on larger climbs that could be better served by ladders.

The heap operations (heappush and heappop) maintain logarithmic time for insertion and removal, allowing the algorithm to process each building in a single pass while keeping the heap size bounded by the number of ladders plus one. This bounded size prevents the heap from growing excessively large, which in turn limits the overhead of heap maintenance.

The early termination check (if bricks < small[0]) prevents further unnecessary iterations once the resource limit is reached. By returning immediately when bricks are insufficient for the smallest pending climb, the function avoids processing the remaining buildings, saving computational effort in cases where the reachable distance is far shorter than the total number of buildings.

Imagine you are walking along a path full of buildings of different heights. You want to see how far you can get. To climb from one building to the next, you sometimes need help if the next roof is higher than where you are standing. You have two types of help available: some bricks to build a ramp and some ladders to climb.

This code explores how far you can go. It watches the difference in height between the building you are on and the next one. If the next building is shorter or the same height, no help is needed at all. If the new building is taller, it keeps track of how much extra height you need to cover.

You should always use your ladders for the biggest height jumps because they are very powerful. The code keeps track of all the jumps you have made using a small collection. Whenever this collection grows larger than the number of ladders you have, it decides that the smallest jump in that group must have been covered by bricks instead of a ladder.

If you do not have enough bricks to cover that smallest jump, then the journey ends at that spot. If you have enough bricks, you spend them and keep moving forward to the next building. The process repeats until you either run out of both bricks and ladders or you successfully reach the very last building in the row.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java				TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		Go
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fpdjsns	C++
	fsq	C++
	halfrost					Go
	JoshCrozier				JS
	lkwq007		Python
	pruthvikp		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
pruthvikp	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality