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:
|
|
Example 2:
|
|
Example 3:
|
|
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) andans
as 0 (number of rungs to add). - Iterate through each rung in
rungs
:
- Calculate the gap between
rung
andprev
. - 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 currentrung
.
- Return
ans
.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(N)
, whereN
is the number of rungs. - 🧺 Space complexity:
O(1)