#1936

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Add Minimum Number of Rungs

Determine the fewest rungs to add to climb a strictly increasing ladder using a greedy step-by-step approach.

Problem Statement

You are given a strictly increasing array rungs representing the heights of ladder rungs. You begin at height 0 and need to reach the topmost rung. You can climb to the next rung only if its height is within a specified distance dist from your current position. New rungs may be inserted at any positive integer height.

Return the minimum number of rungs that must be added to the ladder so that you can reach the last rung. Each added rung should maintain the strictly increasing property, and your climbing never exceeds the maximum distance dist between consecutive steps.

Examples

Example 1

Input: rungs = [1,3,5,10], dist = 2

Output: 2

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

This ladder can be climbed without adding additional rungs.

Example 3

Input: rungs = [3,4,6,7], dist = 2

Output: 1

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 <= 105
1 <= rungs[i] <= 109
1 <= dist <= 109
rungs is strictly increasing.

Solution Approach

Iterate and Calculate Gaps

Loop through each rung starting from the floor, calculate the distance to the next rung, and identify if it exceeds dist. For any gap larger than dist, compute how many intermediate rungs are required using ceiling division to cover the distance without violating the maximum step constraint.

Greedy Insertion

Insert the minimum number of rungs immediately whenever a gap is too large. This greedy choice ensures that each step forward is maximized and no extra rungs are added unnecessarily. The algorithm proceeds sequentially without backtracking.

Maintain Invariant and Sum Additions

Keep track of the total number of added rungs while iterating. The invariant is that after handling each gap, every consecutive rung pair is climbable within dist. Return the cumulative count once the last rung is reachable.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The solution scans the ladder once, performing constant work per rung, resulting in O(n) time where n is the number of rungs. Space is O(1) since only counters and temporary calculations are stored.

What Interviewers Usually Probe

Checks if the candidate identifies the greedy pattern and gap-based approach.
Looks for correct calculation of added rungs without over-insertion.
Observes awareness of strictly increasing constraint and maximum distance invariant.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the gap from the floor to the first rung properly.
Using floor division instead of ceiling, causing undercount of needed rungs.
Not updating the current position after adding intermediate rungs, violating the distance constraint.

Follow-up variants

Allow non-strictly increasing rungs and compute minimal insertions to maintain non-decreasing order within dist.
Use variable distance limits for each rung transition instead of a fixed dist.
Determine the minimal total height of added rungs instead of the count of rungs.

FAQ

What is the key pattern in Add Minimum Number of Rungs?

The problem uses a greedy choice plus invariant validation pattern, maximizing each step before adding new rungs.

How do I handle the floor to first rung gap?

Treat the floor as height 0 and compute the gap to the first rung; insert intermediate rungs if the distance exceeds dist.

Can rungs be added at non-integer heights?

No, rungs must be added at positive integer heights while maintaining strictly increasing order.

What if all gaps are within dist?

No rungs need to be added; the ladder is already climbable.

What is the time complexity of the greedy solution?

Iterating once over the rungs gives O(n) time, where n is the number of rungs; space remains O(1).

terminal

Solution

Solution 1: Greedy + Simulation

According to the problem description, we know that every time we plan to climb a new rung, we need to ensure that the height difference between the new rung and the current position does not exceed `dist`. Otherwise, we need to greedily insert a new rung at a distance of $dist$ from the current position, climb a new rung, and the total number of rungs to be inserted is $\lfloor \frac{b - a - 1}{dist} \rfloor$, where $a$ and $b$ are the current position and the height of the new rung, respectively. The answer is the sum of all inserted rungs.

1

2

3

4

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))

Continue Practicing

#1946 largest number after mutating substring #1921 eliminate maximum number of monsters #1953 maximum number of weeks for which you can work