Add Minimum Number of Rungs: Greedy Gap Filling

You have a ladder with rungs at specific heights, and you start on the ground at height 0. Each step you take can cover at most dist units of height. If a gap between consecutive rungs (or between the ground and the first rung) exceeds dist, you need to insert new rungs to make the ladder climbable. The goal is to find the minimum number of rungs to add.

This is LeetCode 1936: Add Minimum Number of Rungs, a medium problem that rewards a clean greedy scan. Once you see the gap-filling formula, the solution is a short loop with one arithmetic expression per gap.

The approach: greedy gap filling

The key insight is that each gap between consecutive positions can be handled independently. You scan through the rungs in order, and for each gap, you compute how many new rungs you need to insert so that no jump exceeds dist.

For a gap of size g with a maximum climb distance of dist, the number of rungs you need to add is (g - 1) // dist. This works because you are dividing the gap into chunks of size dist. If the gap is exactly divisible by dist, you need g // dist - 1 segments (and therefore that many new rungs). If there is a remainder, you need one more segment. The expression (g - 1) // dist captures both cases in a single formula.

An equivalent way to think about it: you need ceil(g / dist) - 1 new rungs. The ceiling division accounts for any partial segment, and you subtract 1 because the existing rung at the top of the gap does not need to be added.

The code

def add_rungs(rungs, dist):
    added = 0
    prev = 0
    for r in rungs:
        gap = r - prev
        if gap > dist:
            added += (gap - 1) // dist
        prev = r
    return added

1. Initialize added to 0 and prev to 0 (the ground).
2. For each rung height r, compute the gap from the previous position.
3. If the gap exceeds dist, calculate how many intermediate rungs are needed using (gap - 1) // dist and add that to the running total.
4. Update prev to the current rung height.
5. Return the total number of added rungs.

Visual walkthrough

Here is a step-by-step trace through the example rungs = [1, 3, 5, 10] with dist = 2. Each step examines one gap between consecutive positions.

The first three gaps (0 to 1, 1 to 3, 3 to 5) are all within the climb distance of 2, so no new rungs are needed. The final gap from 5 to 10 has size 5, which exceeds dist = 2. Applying the formula: (5 - 1) // 2 = 2 new rungs. The total answer is 2.

Complexity analysis

The algorithm makes a single pass through the rungs array, doing O(1) work per element. It uses only a constant number of variables regardless of input size.

Building blocks

This problem uses two reusable patterns that appear across many LeetCode problems.

1. Greedy single-pass accumulation

The pattern of scanning a sequence from left to right, making a locally optimal decision at each step, and accumulating a global result:

• Jump Game II: count the minimum jumps to reach the end by greedily extending the current range
• Minimum Number of Arrows to Burst Balloons: scan sorted intervals and greedily decide when a new arrow is needed

2. Ceiling division for even spacing

The formula ceil(g / dist) - 1 (or its integer equivalent (g - 1) // dist) computes how many intermediate points are needed to split a range into segments of at most a given size. This shows up whenever you need to partition a distance or quantity into bounded chunks:

• Koko Eating Bananas: compute ceil(piles[i] / speed) hours to eat a pile at a given speed
• Minimum Number of Days to Make m Bouquets: ceiling division to determine how many groups fit into a range

Edge cases

All gaps within reach. If every consecutive gap is already within dist, the answer is 0. The loop runs but never adds anything.

First rung is far from ground. The ground is at height 0. If rungs[0] is much larger than dist, you need (rungs[0] - 1) // dist rungs just to reach the first existing rung. The code handles this naturally since prev starts at 0.

Single rung. If the array has only one element, there is exactly one gap to check (from 0 to that rung). The formula still applies correctly.

Gap exactly equal to dist. When gap == dist, you can reach the next rung in one step. The condition gap > dist correctly skips this case, adding 0 new rungs.

From understanding to recall

You have read the greedy solution and the gap-filling formula makes sense. One pass, one formula, one accumulator. Clean. But can you write it from scratch in an interview without peeking at your notes?

The details matter: starting prev at 0 (not at rungs[0]), using (gap - 1) // dist (not gap // dist), and checking gap > dist (not gap >= dist). These are small distinctions that are easy to confuse under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy gap-filling loop from scratch at increasing intervals. After a few rounds, the formula and loop structure become automatic. You see "minimum insertions to cover gaps" and the code flows out without hesitation. The greedy accumulation pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Jump Game - Another greedy problem about reaching a destination with constrained jumps
• Gas Station - A greedy problem that also involves scanning through sequential positions