Watch 9 video solutions for Add Minimum Number of Rungs, a medium level problem involving Array, Greedy. This walkthrough by Coders Camp has 746 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= rungs[i] <= 1091 <= dist <= 109rungs is strictly increasing.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 | 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. |