LeetCode 1936 - Add Minimum Number of Rungs

The problem gives us a ladder represented by a strictly increasing array called rungs. Each value in the array represents the height of a rung above the floor. You begin standing on the floor at height 0, and your goal is to reach the final rung.

leetcodemediumarraygreedy

LeetCode Problem 1936

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us a ladder represented by a strictly increasing array called rungs. Each value in the array represents the height of a rung above the floor. You begin standing on the floor at height 0, and your goal is to reach the final rung.

The restriction is that you can only climb upward if the vertical distance between your current position and the next rung is at most dist. If a gap is larger than dist, then the ladder is not currently climbable. To fix this, you are allowed to insert additional rungs at any positive integer heights that are not already occupied.

The task is to compute the minimum number of additional rungs required so that every climb from one rung to the next is no more than dist.

The input consists of:

  • rungs, a strictly increasing integer array
  • dist, the maximum climb distance allowed

The output is a single integer representing the smallest number of new rungs needed.

The constraints are important:

  • rungs.length can be as large as 10^5
  • Heights can be as large as 10^9

These limits immediately tell us that any quadratic or simulation-heavy solution will be too slow. We need an algorithm that processes the ladder efficiently in a single pass.

The problem also guarantees that rungs is strictly increasing, which simplifies processing because we never need to handle duplicates or sorting.

Several edge cases are important:

  • The first rung may already be reachable from the floor
  • The first rung may require multiple inserted rungs
  • Large gaps may require many inserted rungs
  • dist may be 1, forcing every height difference to be exactly one
  • The ladder may already be valid and require no insertions

A naive implementation can easily make off-by-one mistakes when calculating how many rungs are needed inside a gap.

Approaches

Brute Force Approach

A straightforward approach is to simulate climbing the ladder step by step.

For every gap between the current position and the next rung:

  • If the gap is at most dist, move directly to the next rung
  • Otherwise, repeatedly insert a new rung exactly dist units higher than the current position until the next original rung becomes reachable

This approach is correct because each inserted rung maximizes the climb distance while keeping the ladder valid. However, it may perform many repeated operations for large gaps.

For example, if the gap is 1,000,000,000 and dist = 1, we would simulate nearly a billion insertions. That is far too slow.

Optimal Greedy Approach

The key observation is that we do not need to explicitly simulate every inserted rung.

Suppose the gap between two reachable positions is:

gap = next_rung - current_position

If gap <= dist, no new rungs are needed.

Otherwise, we must divide the gap into smaller segments whose lengths are all at most dist.

For a gap of size gap, the minimum number of inserted rungs is:

(gap - 1) // dist

Why does this formula work?

If a gap is exactly divisible by dist, we need one fewer inserted rung than the quotient because the final jump lands directly on the target rung.

Examples:

  • gap = 6, dist = 2

  • We need jumps: 2, 2, 2

  • Inserted rungs: 2

  • Formula: (6 - 1) // 2 = 2

  • gap = 5, dist = 2

  • We need jumps: 2, 2, 1

  • Inserted rungs: 2

  • Formula: (5 - 1) // 2 = 2

This lets us process each gap in constant time.

Approach Time Complexity Space Complexity Notes
Brute Force O(total inserted rungs) O(1) Simulates every inserted rung individually
Optimal O(n) O(1) Computes required insertions mathematically

Algorithm Walkthrough

  1. Initialize a variable called previous_height to 0 because we start on the floor.
  2. Initialize a counter called added_rungs to 0. This will track the total number of inserted rungs.
  3. Iterate through every rung height in the rungs array.
  4. For each rung, compute the gap between the current rung and the previous reachable position:
gap = rung - previous_height
  1. If gap <= dist, the current rung is directly reachable. No additional work is needed.
  2. If gap > dist, compute how many extra rungs are required:
needed = (gap - 1) // dist

This formula gives the minimum number of inserted rungs necessary to ensure every jump is at most dist. 7. Add needed to added_rungs. 8. Update previous_height to the current rung height because we can now stand on this rung. 9. Continue until all rungs are processed. 10. Return added_rungs.

Why it works

The greedy strategy works because every gap is independent. To minimize inserted rungs, we always want each jump to be as large as possible while remaining within dist.

For a gap of size gap, dividing it into segments of maximum allowed length minimizes the number of inserted rungs. The formula (gap - 1) // dist computes exactly how many intermediate points are needed.

Since we process every gap optimally and independently, the total number of inserted rungs is globally minimal.

Python Solution

from typing import List

class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        added_rungs = 0
        previous_height = 0

        for rung in rungs:
            gap = rung - previous_height

            if gap > dist:
                added_rungs += (gap - 1) // dist

            previous_height = rung

        return added_rungs

The implementation follows the algorithm directly.

The variable previous_height tracks the last reachable position. Initially, this is the floor at height 0.

For each rung, we calculate the gap between the current rung and the previous position. If the gap exceeds dist, we compute how many additional rungs are needed using integer division.

The expression (gap - 1) // dist is the critical part of the solution. It avoids off-by-one errors and correctly handles cases where the gap is exactly divisible by dist.

The algorithm processes the array in one pass and uses only constant extra memory.

Go Solution

func addRungs(rungs []int, dist int) int {
    addedRungs := 0
    previousHeight := 0

    for _, rung := range rungs {
        gap := rung - previousHeight

        if gap > dist {
            addedRungs += (gap - 1) / dist
        }

        previousHeight = rung
    }

    return addedRungs
}

The Go implementation is nearly identical to the Python version.

Go integer division automatically truncates toward zero, which is exactly what we want for the formula (gap - 1) / dist.

No special handling is required for empty slices because the constraints guarantee at least one rung.

The maximum possible answer fits safely within Go's int type under standard LeetCode environments.

Worked Examples

Example 1

Input:

rungs = [1,3,5,10]
dist = 2

Initial state:

previous_height = 0
added_rungs = 0
Current Rung Gap Needed Additions Total Added New Previous
1 1 0 0 1
3 2 0 0 3
5 2 0 0 5
10 5 (5 - 1) // 2 = 2 2 10

Final answer:

2

Inserted rungs could be at heights 7 and 8.

Example 2

Input:

rungs = [3,6,8,10]
dist = 3

Initial state:

previous_height = 0
added_rungs = 0
Current Rung Gap Needed Additions Total Added New Previous
3 3 0 0 3
6 3 0 0 6
8 2 0 0 8
10 2 0 0 10

Final answer:

0

The ladder is already climbable.

Example 3

Input:

rungs = [3,4,6,7]
dist = 2

Initial state:

previous_height = 0
added_rungs = 0
Current Rung Gap Needed Additions Total Added New Previous
3 3 (3 - 1) // 2 = 1 1 3
4 1 0 1 4
6 2 0 1 6
7 1 0 1 7

Final answer:

1

A rung can be inserted at height 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each rung is processed exactly once
Space O(1) Only a few integer variables are used

The algorithm performs a single linear scan through the input array. Every operation inside the loop is constant time arithmetic.

No auxiliary data structures are required, so the memory usage remains constant regardless of input size.

Test Cases

from typing import List

class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        added_rungs = 0
        previous_height = 0

        for rung in rungs:
            gap = rung - previous_height

            if gap > dist:
                added_rungs += (gap - 1) // dist

            previous_height = rung

        return added_rungs

sol = Solution()

assert sol.addRungs([1,3,5,10], 2) == 2  # provided example 1
assert sol.addRungs([3,6,8,10], 3) == 0  # provided example 2
assert sol.addRungs([3,4,6,7], 2) == 1  # provided example 3

assert sol.addRungs([1], 1) == 0  # single reachable rung
assert sol.addRungs([2], 1) == 1  # single unreachable rung
assert sol.addRungs([10], 2) == 4  # multiple insertions before first rung

assert sol.addRungs([2,4,6,8], 2) == 0  # perfectly spaced ladder
assert sol.addRungs([5,10,15], 5) == 0  # all gaps equal dist

assert sol.addRungs([5], 10) == 0  # dist larger than gap
assert sol.addRungs([100], 1) == 99  # maximum insertions pattern

assert sol.addRungs([1,1000000000], 1) == 999999998  # very large gap
assert sol.addRungs([1,2,3,4,5], 1) == 0  # already fully connected

assert sol.addRungs([4,8,12], 3) == 3  # repeated insertion requirement
assert sol.addRungs([7,14], 4) == 2  # exact divisibility edge case
Test Why
[1,3,5,10], dist=2 Standard case with a large final gap
[3,6,8,10], dist=3 No insertions needed
[3,4,6,7], dist=2 First rung unreachable
[1], dist=1 Smallest valid reachable input
[2], dist=1 Single insertion before first rung
[10], dist=2 Multiple insertions before first rung
[2,4,6,8], dist=2 Every gap exactly equals dist
[5,10,15], dist=5 Exact divisibility throughout
[5], dist=10 Large dist value
[100], dist=1 Worst-case insertion density
[1,1000000000], dist=1 Stress test with huge gap
[1,2,3,4,5], dist=1 Fully connected ladder
[4,8,12], dist=3 Repeated insertion logic
[7,14], dist=4 Off-by-one divisibility validation

Edge Cases

One important edge case occurs when the first rung itself is unreachable from the floor. Since the climb starts at height 0, the very first gap may already violate the dist limit. A careless implementation might only compare adjacent rungs and forget the floor entirely. This solution avoids that issue by initializing previous_height to 0.

Another important edge case is when a gap is exactly divisible by dist. For example, if the gap is 6 and dist is 2, we need only two inserted rungs, not three. Incorrect formulas like gap // dist would overcount. Using (gap - 1) // dist correctly handles exact divisibility cases.

Large gaps are another common source of bugs. With constraints up to 10^9, explicitly simulating inserted rungs would be extremely slow. This implementation computes the required insertions mathematically in constant time, allowing it to handle massive gaps efficiently.

A final edge case occurs when no insertions are needed at all. Every gap may already satisfy the distance constraint. The algorithm naturally handles this because it only adds to the answer when gap > dist.