We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Add Minimum Number of Rungs

Number: 2066

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given a strictly increasing integer array rungs representing the heights of rungs on a ladder. Starting at the floor (height 0), your goal is to reach the highest rung. You can only move to the next rung if the vertical distance from your current position to the next rung is at most dist. You are allowed to add rungs at any positive integer heights where one does not already exist. Return the minimum number of rungs that need to be added so that you can climb the ladder.

Key Insights

  • The problem revolves around ensuring all gaps (between the current position and the next rung) are no larger than the allowed distance dist.
  • Start by checking the gap from the ground (height 0) to the first rung.
  • For each consecutive rung, if the gap is more than dist, calculate the number of rungs needed to cover this gap.
  • The formula (gap - 1) // dist gives the minimal rungs needed for any gap that exceeds dist.
  • A greedy approach works here — handle each gap independently to minimize the total additions.

Space and Time Complexity

Time Complexity: O(n) where n is the number of rungs, as we traverse the array once. Space Complexity: O(1) additional space.

Solution

We iterate from the ground (0) to each rung, computing the gap between our current position and the next rung. If the gap exceeds dist, we calculate how many rungs we must add using the formula: additionalRungs = (gap - 1) // dist. This formula captures the idea of breaking the gap into segments of at most dist. Sum these additional rungs across all gaps to get the final count. Data structures used are a simple integer counter and iteration over the array, making this a straightforward greedy approach.

Code Solutions

# Python solution with detailed comments

def addRungs(rungs, dist):
    # Initialize additional rungs count and current height starting from the ground (0)
    additional_rungs = 0
    current_height = 0
    
    # Iterate over each rung in the ladder
    for rung in rungs:
        # Compute the gap between current height and the current rung
        gap = rung - current_height
        # If gap is larger than allowed distance, calculate extra rungs needed
        if gap > dist:
            additional_rungs += (gap - 1) // dist
        # Update the current height to the current rung
        current_height = rung
    
    return additional_rungs

# Example usage:
# Input: rungs = [1,3,5,10], dist = 2, Expected output: 2
print(addRungs([1,3,5,10], 2))
← Back to All Questions