Add Minimum Number of Rungs - Practice Coding Problems

Add Minimum Number of Rungs - Problem

Array Greedy Medium

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.

Input & Output

Example 1 — Basic Gap Filling

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

› Output: 2

💡 Note: Gap from 0→1 is 1 (≤2, ok). Gap from 1→3 is 2 (≤2, ok). Gap from 3→5 is 2 (≤2, ok). Gap from 5→10 is 5 (>2), need (5-1)/2 = 2 rungs at heights 7 and 9.

Example 2 — Multiple Small Gaps

$ Input: rungs = [3,6,8,10], dist = 3

› Output: 0

💡 Note: Gap 0→3 is 3 (≤3, ok). Gap 3→6 is 3 (≤3, ok). Gap 6→8 is 2 (≤3, ok). Gap 8→10 is 2 (≤3, ok). No additional rungs needed.

Example 3 — Large Initial Gap

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

› Output: 1

💡 Note: Gap 0→3 is 3 (>2), need (3-1)/2 = 1 rung. All other gaps are ≤2. Total: 1 rung.

Constraints

1 ≤ rungs.length ≤ 10⁵
1 ≤ rungs[i] ≤ 10⁹
1 ≤ dist ≤ 10⁹
rungs is strictly increasing

Visualization

Tap to expand

Understanding the Visualization

Input

Ladder rungs at [1,3,5,10] with max step dist=2

Process

Check each gap: 0→1 (ok), 1→3 (ok), 3→5 (ok), 5→10 (too big)

Output

Need 2 additional rungs for the 5→10 gap

Key Takeaway

🎯 Key Insight: Use formula (gap-1)/dist to find minimum rungs for each large gap

Asked in

G Google 12 a Amazon 8 M Microsoft 6 f Meta 4

The key insight is to use a greedy approach: for each gap larger than dist, add exactly (gap-1)/dist rungs. This gives the minimum number since we can space added rungs exactly dist apart. Best approach is greedy with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Optimal Gap Filling	O(n)	O(1)	Add minimum rungs needed for each gap larger than dist
Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible rung placements and find minimum

Greedy - Optimal Gap Filling — Algorithm Steps

Start from height 0
For each rung, check gap from current position
If gap > dist, add (gap-1)/dist rungs
Continue to next rung

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Gap

Calculate distance to next rung

Add Rungs

Add minimum rungs if gap > dist

Continue

Move to next rung and repeat

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* rungs, int rungsSize, int dist) {
    int added = 0;
    int currentHeight = 0;
    
    for (int i = 0; i < rungsSize; i++) {
        int gap = rungs[i] - currentHeight;
        if (gap > dist) {
            int needed = (gap - 1) / dist;
            added += needed;
        }
        currentHeight = rungs[i];
    }
    
    return added;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int rungs[1000];
    int rungsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        rungs[rungsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int dist;
    scanf("%d", &dist);
    
    printf("%d\n", solution(rungs, rungsSize, dist));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the rungs array, checking each gap once

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current position and count

✓ Linear Space

26.3K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Optimal Gap Filling — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler