Abstract / Summary

You must add the fewest rungs so a person can climb from the bottom to the top without jumping more than a given distance.

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 44% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy

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 addRungs method determines how many additional rungs must be inserted into a ladder so that a climber can ascend from the ground to the highest existing rung while never stepping more than dist units between consecutive points. The algorithm treats the ground as an initial rung at height 0, then iteratively moves upward, using binary search to locate the farthest reachable existing rung. When a gap larger than dist is encountered, the required number of intermediate rungs is computed directly and added to the result.

Key Steps

Initialization

result = 0
rungs  = [0] + rungs
height = 0
pos    = 0

The variable result accumulates the count of new rungs. By prefixing the input list with 0, the ground level becomes part of the searchable sequence. height tracks the current altitude, and pos remembers the index of the last rung that was reached, allowing the subsequent search to start from that point.

Main Loop

while height < rungs[-1]:
    next = bisect_right(rungs, height + dist, pos) - 1
    if next == len(rungs):
        break

The loop continues until the climber reaches or surpasses the highest original rung. bisect_right performs a binary search in the sub-array beginning at pos, locating the insertion point for height + dist. Subtracting one yields the index of the highest rung that lies within a single step from the current height. If the search returns an index equal to the length of the list, the top has been reached and the loop exits.

Handling Gaps

if next == pos:
    gap     = rungs[next + 1] - height
    result += (gap - 1) // dist
    next   += 1

When the binary search cannot advance beyond the current position (next == pos), the distance to the next existing rung exceeds dist. The code computes the size of this gap and determines how many extra rungs are needed by integer division of (gap-1) by dist. The calculation yields the minimal number of evenly spaced intermediate rungs that guarantee each step stays within the allowed distance. After inserting the virtual rungs, next is advanced to the following original rung.

Updating Position

pos    = next
height = rungs[next]

The current position and height are updated to reflect the newly reached rung, preparing the algorithm for the next iteration of the loop.

Edge Cases Handled

The algorithm gracefully manages the situation where the maximum step distance dist is large enough to reach the final rung directly; the binary search will locate the top rung in the first iteration, causing the loop to terminate without adding any extra rungs. It also correctly processes a ladder whose consecutive rungs are spaced farther apart than dist; the gap-handling block computes the exact number of required intermediate rungs, even when the gap is a multiple of dist or when only a single extra rung is needed. Additionally, by inserting a ground rung at height 0, the code works uniformly whether the original list starts at a height greater than zero or already includes a zero height.

Performance Optimizations

The use of bisect_right provides a logarithmic-time search for the farthest reachable rung, avoiding a linear scan of the entire list on each iteration. By passing the current pos as the left boundary to the binary search, the algorithm restricts the search space to the yet-unexplored portion of the ladder, preventing redundant comparisons. The calculation of required extra rungs with the expression (gap - 1) // dist eliminates the need for an inner loop that would otherwise add rungs one by one, thereby reducing the overall number of operations. These choices together ensure that the method processes large inputs efficiently while maintaining a clear and concise control flow.

Imagine a tall ladder that goes all the way up into the clouds. The rungs are the steps on the ladder, but they are not all evenly spaced. Some gaps between the rungs are very large, and those are too wide for little legs to reach.

A list is created that starts at the very bottom, right at zero, to make things easy to track. A counter starts at zero to keep track of how many extra rungs might need to be added to bridge those big gaps.

The code looks at where the feet are currently standing and checks how far up the ladder they can reach in one big stretch. If the very next rung is too far away, some extra steps are added between the current spot and that next rung. The number of extra steps depends on how wide the gap is. If the gap is small, maybe only one step is needed, but if the gap is massive, several extra steps are placed.

After adding the necessary rungs, the climber moves up to the new highest spot reached. This pattern repeats, checking the next gap and adding more rungs if needed, until the very top of the ladder is reached. Everything stays focused on making sure the climber can safely move from one step to the next without ever getting stuck.

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++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++		Java	Python		Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	MacJim	C++
	suxrobGM					C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
suxrobGM	C#
varunu28	Java

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