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.
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; }}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.