Add Minimum Number of Rungs
MedPrompt
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 <= 109rungsis strictly increasing.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process of climbing the ladder. We iterate through the rungs, and for each gap between the current position and the next rung, we check if it's climbable. If the gap is too large, we simulate adding rungs one by one, each time advancing our position by dist, until the next rung is reachable.
Algorithm
- Initialize
rungsAdded = 0andcurrentHeight = 0. - For each
rungin therungsarray:- While the gap
rung - currentHeightis greater thandist:- Increment
rungsAddedas we need to add a rung. - Advance our position by
dist:currentHeight += dist.
- Increment
- Once the current
rungis reachable, updatecurrentHeight = rung.
- While the gap
- Return
rungsAdded.
Walkthrough
This method directly models the physical process of climbing. We maintain a variable currentHeight representing our current position on the ladder (initially 0, the floor) and a counter rungsAdded for the number of rungs we add.
We iterate through the rungs array, considering each rung as our next target. For each targetRung, we check if the difference targetRung - currentHeight is greater than dist. If it is, we are unable to make the climb in one step. We then enter a loop where we repeatedly add a rung. In each iteration of this inner loop, we increment rungsAdded and advance our currentHeight by dist. This loop continues until the remaining distance to targetRung is less than or equal to dist.
Once the targetRung is reachable, we update currentHeight to the height of the targetRung and move to the next rung in the array. This process is repeated for all rungs, and the final value of rungsAdded is the result.
class Solution { public int addRungs(int[] rungs, int dist) { int rungsAdded = 0; int currentHeight = 0; for (int rung : rungs) { // While the next rung is unreachable while (rung - currentHeight > dist) { // Add a rung at the maximum possible distance currentHeight += dist; rungsAdded++; } // Climb to the existing rung currentHeight = rung; } return rungsAdded; }}Complexity
Time
O(S / dist), where S is the height of the last rung. The complexity is not dependent on N (the number of rungs) but on the magnitude of the values in `rungs`. In the worst case, `rungs = [10^9]` and `dist = 1`, the inner loop can run up to 10^9 times, which is too slow.
Space
O(1), as we only use a few variables to store the current state, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement as it directly mirrors the problem statement.
Cons
Extremely inefficient for large gaps between rungs or a small
distvalue.Will likely result in a Time Limit Exceeded (TLE) error for many test cases due to its high time complexity.
This approach improves upon the simulation by calculating the number of rungs needed for a large gap in a single mathematical operation instead of simulating each step. It's a greedy approach because for each gap, we add the minimum number of rungs required to bridge it, and this local optimization leads to a global optimum since choices for one gap don't affect subsequent gaps.
Algorithm
- Initialize
rungsAdded = 0andcurrentHeight = 0. - For each
rungin therungsarray:- Calculate the gap:
gap = rung - currentHeight. - If
gap > dist:- Calculate the number of rungs to add for this gap using the formula:
numToAdd = (gap - 1) / dist. - Add this number to the total:
rungsAdded += numToAdd.
- Calculate the number of rungs to add for this gap using the formula:
- Update
currentHeight = rung.
- Calculate the gap:
- Return
rungsAdded.
Walkthrough
This optimal solution avoids the slow simulation of the brute-force approach. We iterate through the rungs once, keeping track of our currentHeight (starting at 0).
For each rung, we calculate the gap = rung - currentHeight. If this gap is larger than dist, we must add rungs. To find the minimum number of rungs to add, we should place them as far apart as possible, i.e., at a distance of dist from each other. The number of rungs needed to cover a gap can be calculated efficiently with the formula (gap - 1) / dist using integer division. This formula correctly computes ceil(gap / dist) - 1.
For example, if the gap is 5 and dist is 2, (5-1)/2 = 2 rungs are needed. We add this calculated number to our total count of rungsAdded.
After processing the gap (and adding rungs if necessary), we update our currentHeight to the height of the current rung. We continue this for all rungs and return the total count.
class Solution { public int addRungs(int[] rungs, int dist) { int rungsAdded = 0; int currentHeight = 0; for (int rung : rungs) { int gap = rung - currentHeight; if (gap > dist) { // Calculate how many rungs are needed for this gap. // Each new rung can cover 'dist' height. // The number of rungs needed is ceil(gap / dist) - 1. // Using integer arithmetic, this is (gap - 1) / dist. rungsAdded += (gap - 1) / dist; } currentHeight = rung; } return rungsAdded; }}Complexity
Time
O(N), where N is the number of rungs in the input array. We iterate through the array once, and each step involves a constant number of arithmetic operations.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Highly efficient and optimal solution with linear time complexity.
Handles large values of rung heights and distances without performance degradation.
Cons
Requires a small mathematical insight to derive the formula, which might be slightly less intuitive than direct simulation.
Solutions
Solution
class Solution {public int addRungs(int[] rungs, int dist) { int ans = 0, prev = 0; for (int x : rungs) { ans += (x - prev - 1) / dist; prev = x; } return ans; }}class Solution: def addRungs(self, rungs: List[int], dist: int) -> int: rungs = [0] + rungs return sum((b - a - 1) // dist for a, b in pairwise(rungs))class Solution {public: int addRungs(vector<int> &rungs, int dist) { int ans = 0, prev = 0; for (int &x : rungs) { ans += (x - prev - 1) / dist; prev = x; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.