Add Minimum Number of Rungs

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.

Examples

Example 1:

1
2
3
4
5
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:

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

Example 3:

1
2
3
4
5
6
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^5
1 <= rungs[i] <= 10^9
1 <= dist <= 10^9
rungs is strictly increasing.

Solution

Method 1 – Greedy Gap Filling

Intuition

The key idea is to always fill the largest possible gap with the fewest rungs. For each gap between the current position and the next rung, if the gap exceeds dist, we add enough rungs to ensure every step is at most dist. This greedy approach works because adding rungs at the maximum allowed distance minimizes the total number of rungs needed.

Approach

Initialize prev as 0 (the ground) and ans as 0 (number of rungs to add).
Iterate through each rung in rungs:

Calculate the gap between rung and prev.
If the gap is greater than dist, compute how many rungs are needed: (gap - 1) // dist.
Add this number to ans.
Update prev to the current rung.

Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
   int addRungs(vector<int>& rungs, int dist) {
      int ans = 0, prev = 0;
      for (int rung : rungs) {
        int gap = rung - prev;
        if (gap > dist) {
           ans += (gap - 1) / dist;
        }
        prev = rung;
      }
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
   public int addRungs(int[] rungs, int dist) {
      int ans = 0, prev = 0;
      for (int rung : rungs) {
        int gap = rung - prev;
        if (gap > dist) {
           ans += (gap - 1) / dist;
        }
        prev = rung;
      }
      return ans;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
   def addRungs(self, rungs: list[int], dist: int) -> int:
      ans: int = 0
      prev: int = 0
      for rung in rungs:
        gap: int = rung - prev
        if gap > dist:
           ans += (gap - 1) // dist
        prev = rung
      return ans

Complexity

⏰ Time complexity: O(N), where N is the number of rungs.
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 – Greedy Gap Filling#

Intuition#

Approach#

Code#

Complexity#