1936. Add Minimum Number of Rungs - Solution

The problem

You are given a strictly increasing integer array rungs that represents the height of rungs on a ladder. You are currently on the floor at height 0, and you want to reach the last rung.

You are also given an integer dist. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is at most dist. You are able to insert rungs at any positive integer height if a rung is not already there.

Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.

Example 1:

Input: rungs = [1,3,5,10], dist = 2
Output: 2
Explanation:
You currently cannot reach the last rung.
Add rungs at heights 7 and 8 to climb this ladder. 
The ladder will now have rungs at [1,3,5,7,8,10].

Example 2:

Input: rungs = [3,6,8,10], dist = 3
Output: 0
Explanation:
This ladder can be climbed without adding additional rungs.

Example 3:

Input: rungs = [3,4,6,7], dist = 2
Output: 1
Explanation:
You currently cannot reach the first rung from the ground.
Add a rung at height 1 to climb this ladder.
The ladder will now have rungs at [1,3,4,6,7].

Constraints:

1 <= rungs.length <= 10⁵
1 <= rungs[i] <= 10⁹
1 <= dist <= 10⁹
rungs is strictly increasing.

Approach overview

Problem Overview: You climb a ladder where each rung height is given in a strictly increasing array. You can only climb up to dist units at a time. If the gap between consecutive rungs exceeds dist, you must insert additional rungs. The task is to compute the minimum number of new rungs required so every climb step stays within the allowed distance.

Approach 1: Greedy Approach (O(n) time, O(1) space)

The ladder is already sorted by height, so a single pass works. Track the previous reachable height starting from ground level 0. For each rung r, compute the gap r - prev. If the gap is greater than dist, you must insert extra rungs between them. The number of required rungs is (gap - 1) / dist, which directly tells how many evenly spaced steps are needed so no step exceeds dist. Add that count to the answer, then move prev to the current rung. This greedy rule works because placing rungs as far apart as allowed minimizes insertions. The algorithm only iterates once over the array and uses constant extra memory.

This approach fits naturally with greedy algorithms: at each gap you locally insert the minimum number of rungs needed to satisfy the constraint. No backtracking or restructuring of earlier decisions is required because each segment is independent.

Approach 2: Modified Greedy with Condition Check (O(n) time, O(1) space)

A slightly more explicit version performs the same greedy reasoning but handles the calculation step-by-step. Iterate through the ladder and check if r - prev > dist. When the condition holds, repeatedly add virtual rungs spaced by dist until the remaining gap becomes valid. Each insertion increments the counter and moves the temporary position forward. Once the remaining distance fits within dist, continue to the real rung.

This version is conceptually straightforward and sometimes easier to reason about in interviews because it mirrors the physical process of climbing the ladder. However, instead of repeatedly inserting rungs, you can collapse the logic into the arithmetic formula used in the previous approach. Both rely on the same greedy insight and linear traversal of the array.

Recommended for interviews: The arithmetic greedy solution is what most interviewers expect. It shows you recognized the pattern that each oversized gap can be solved independently using (gap - 1) / dist. Walking through the step-by-step insertion logic first demonstrates understanding of the problem mechanics, while the optimized greedy calculation demonstrates strong algorithmic thinking.

Approach 1: Greedy Approach

The greedy approach involves iterating through each rung in the list and checking the distance from the current position (starting at 0). For each gap between the current position and the next rung that exceeds the maximum allowable distance 'dist', add new rungs in multiples of 'dist' up to the next rung. This minimizes the number of new rungs while ensuring you can move to the next available rung.

Python

def add_rungs(rungs, dist):
    current_height = 0
    additions = 0
    
    for rung in rungs:
        if rung - current_height > dist:
            additions += (rung - current_height - 1) // dist
        current_height = rung
    return additions

# Example usage:
rungs = [1, 3, 5, 10]
dist = 2
print(add_rungs(rungs, dist))  # Output: 2

Java

public class Solution {
    public int addRungs(int[] rungs, int dist) {
        int currentHeight = 0;
        int additions = 0;
        
        for (int rung : rungs) {
            if (rung - currentHeight > dist) {
                additions += (rung - currentHeight - 1) / dist;
            }
            currentHeight = rung;
        }
        return additions;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] rungs = {1, 3, 5, 10};
        int dist = 2;
        System.out.println(sol.addRungs(rungs, dist)); // Output: 2
    }
}

C++

#include <vector>
#include <iostream>

int addRungs(std::vector<int>& rungs, int dist) {
    int currentHeight = 0;
    int additions = 0;
    
    for (int rung : rungs) {
        if (rung - currentHeight > dist) {
            additions += (rung - currentHeight - 1) / dist;
        }
        currentHeight = rung;
    }
    return additions;
}

int main() {
    std::vector<int> rungs = {1, 3, 5, 10};
    int dist = 2;
    std::cout << addRungs(rungs, dist) << std::endl; // Output: 2
    return 0;
}

JavaScript

function addRungs(rungs, dist) {
    let currentHeight = 0;
    let additions = 0;

    for (let rung of rungs) {
        if (rung - currentHeight > dist) {
            additions += Math.floor((rung - currentHeight - 1) / dist);
        }
        currentHeight = rung;
    }
    return additions;
}

let rungs = [1, 3, 5, 10];
let dist = 2;
console.log(addRungs(rungs, dist)); // Output: 2

#include <stdio.h>

int addRungs(int* rungs, int rungsSize, int dist) {
    int currentHeight = 0;
    int additions = 0;
    
    for (int i = 0; i < rungsSize; i++) {
        if (rungs[i] - currentHeight > dist) {
            additions += (rungs[i] - currentHeight - 1) / dist;
        }
        currentHeight = rungs[i];
    }
    return additions;
}

int main() {
    int rungs[] = {1, 3, 5, 10};
    int dist = 2;
    printf("%d\n", addRungs(rungs, 4, dist)); // Output: 2
    return 0;
}

using System;

public class Solution {
    public int AddRungs(int[] rungs, int dist) {
        int currentHeight = 0;
        int additions = 0;

        foreach (int rung in rungs) {
            if (rung - currentHeight > dist) {
                additions += (rung - currentHeight - 1) / dist;
            }
            currentHeight = rung;
        }
        return additions;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] rungs = { 1, 3, 5, 10 };
        int dist = 2;
        Console.WriteLine(sol.AddRungs(rungs, dist)); // Output: 2
    }
}

This Python solution calculates the required additional rungs if there’s a gap greater than dist between consecutive heights.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Modified Greedy with Condition Check

This modified greedy approach is similar to the primary one but involves a more detailed explanation regarding the condition check and the insertion of rungs.

Python

def add_rungs(rungs, dist):
    current_height = 0
    additions = 0
    
    for rung in rungs:
        gap = rung - current_height
        if gap > dist:
            additions += (gap - 1) // dist
        current_height = rung
    return additions

# Example usage:
rungs = [1, 3, 5, 10]
dist = 2
print(add_rungs(rungs, dist))  # Output: 2

Java

public class Solution {
    public int addRungs(int[] rungs, int dist) {
        int currentHeight = 0;
        int additions = 0;
        
        for (int rung : rungs) {
            int gap = rung - currentHeight;
            if (gap > dist) {
                additions += (gap - 1) / dist;
            }
            currentHeight = rung;
        }
        return additions;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] rungs = {1, 3, 5, 10};
        int dist = 2;
        System.out.println(sol.addRungs(rungs, dist)); // Output: 2
    }
}

C++

#include <vector>
#include <iostream>

int addRungs(std::vector<int>& rungs, int dist) {
    int currentHeight = 0;
    int additions = 0;

    for (int rung : rungs) {
        int gap = rung - currentHeight;
        if (gap > dist) {
            additions += (gap - 1) / dist;
        }
        currentHeight = rung;
    }
    return additions;
}

int main() {
    std::vector<int> rungs = {1, 3, 5, 10};
    int dist = 2;
    std::cout << addRungs(rungs, dist) << std::endl; // Output: 2
    return 0;
}

JavaScript

function addRungs(rungs, dist) {
    let currentHeight = 0;
    let additions = 0;

    for (let rung of rungs) {
        let gap = rung - currentHeight;
        if (gap > dist) {
            additions += Math.floor((gap - 1) / dist);
        }
        currentHeight = rung;
    }
    return additions;
}

let rungs = [1, 3, 5, 10];
let dist = 2;
console.log(addRungs(rungs, dist)); // Output: 2

#include <stdio.h>

int addRungs(int* rungs, int rungsSize, int dist) {
    int currentHeight = 0;
    int additions = 0;
    
    for (int i = 0; i < rungsSize; i++) {
        if (rungs[i] - currentHeight > dist) {
            int gap = rungs[i] - currentHeight;
            additions += (gap - 1) / dist;
        }
        currentHeight = rungs[i];
    }
    return additions;
}

int main() {
    int rungs[] = {1, 3, 5, 10};
    int dist = 2;
    printf("%d\n", addRungs(rungs, 4, dist)); // Output: 2
    return 0;
}

using System;

public class Solution {
    public int AddRungs(int[] rungs, int dist) {
        int currentHeight = 0;
        int additions = 0;

        foreach (int rung in rungs) {
            int gap = rung - currentHeight;
            if (gap > dist) {
                additions += (gap - 1) / dist;
            }
            currentHeight = rung;
        }
        return additions;
    }

    public static void Main() {
        Solution sol = new Solution();
        int[] rungs = { 1, 3, 5, 10 };
        int dist = 2;
        Console.WriteLine(sol.AddRungs(rungs, dist)); // Output: 2
    }
}

In this variant, we introduce a variable to store the height gap which increases clarity when processing each rung.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Greedy + Simulation

According to the problem description, we know that every time we plan to climb a new rung, we need to ensure that the height difference between the new rung and the current position does not exceed dist. Otherwise, we need to greedily insert a new rung at a distance of dist from the current position, climb a new rung, and the total number of rungs to be inserted is \lfloor \frac{b - a - 1}{dist} \rfloor, where a and b are the current position and the height of the new rung, respectively. The answer is the sum of all inserted rungs.

The time complexity is O(n), where n is the length of rungs. The space complexity is O(1).

TypeScript

function addRungs(rungs: number[], dist: number): number {
    let ans = 0;
    let prev = 0;
    for (const x of rungs) {
        ans += ((x - prev - 1) / dist) | 0;
        prev = x;
    }
    return ans;
}

func addRungs(rungs []int, dist int) (ans int) {
	prev := 0
	for _, x := range rungs {
		ans += (x - prev - 1) / dist
		prev = x
	}
	return
}

Rust

impl Solution {
    pub fn add_rungs(rungs: Vec<i32>, dist: i32) -> i32 {
        let mut ans = 0;
        let mut prev = 0;

        for &x in rungs.iter() {
            ans += (x - prev - 1) / dist;
            prev = x;
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(n) Space Complexity: O(1)
Modified Greedy with Condition Check	Time Complexity: O(n) Space Complexity: O(1)
Greedy + Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Arithmetic Calculation	O(n)	O(1)	Best general solution. Efficient single pass using formula (gap - 1) / dist.
Modified Greedy with Condition Check	O(n)	O(1)	Useful for understanding the insertion process step by step during interviews.

Frequently asked questions

Is Add Minimum Number of Rungs easy or hard?

The problem is rated Medium because the greedy observation is not immediately obvious to some candidates. Once you recognize that each gap can be handled independently with a simple formula, the implementation becomes straightforward.

Add Minimum Number of Rungs Python/Java solution

Both Python and Java implementations follow the same greedy formula. Iterate through the array, compute gap = rung - prev, and increase the answer by (gap - 1) / dist whenever the gap is too large. The logic is identical across C++, Java, Python, C#, and JavaScript with O(n) time complexity.

How to solve Add Minimum Number of Rungs in O(n)?

Start from ground height 0 and iterate through the sorted rung array. For each rung r, compute the gap r - prev. If the gap exceeds dist, calculate required insertions using (gap - 1) / dist and add it to the result. Update prev to r and continue until all rungs are processed.

What is the best approach for Add Minimum Number of Rungs?

The optimal method is a greedy approach that processes the ladder in one pass. For each gap between consecutive heights, calculate how many extra rungs are needed using (gap - 1) / dist. This ensures the maximum allowed climb distance is never exceeded while minimizing insertions. The algorithm runs in O(n) time and O(1) space.

Is Add Minimum Number of Rungs asked at Google/Amazon/Meta?

Greedy array problems with gap analysis frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary in wording, the pattern of minimizing insertions between ordered values is a common interview theme.

What data structure is used in Add Minimum Number of Rungs?

The problem mainly uses an array to store rung heights. No additional data structures are required because the ladder is already sorted. The solution relies on greedy reasoning and simple arithmetic rather than complex structures.

What is the time complexity of Add Minimum Number of Rungs?

The time complexity is O(n) because the algorithm scans the rung array exactly once. Each step computes the distance to the previous rung and applies a constant-time arithmetic formula. Space complexity is O(1) since only a few variables are maintained.

Add Minimum Number of Rungs solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Modified Greedy with Condition Check

Approach 3: Greedy + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Add Minimum Number of Rungs solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Modified Greedy with Condition Check

Approach 3: Greedy + Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems