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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Potholes That Can Be Fixed

Number: 3425

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

We are given a road represented as a string containing only the characters "x" and "." where "x" denotes a pothole and "." denotes smooth road. A repair operation can fix n consecutive potholes for a cost of n+1. Given a total budget, the goal is to select one or more repair operations (each on a contiguous segment of potholes) such that the total cost does not exceed the budget and the number of potholes fixed is maximized. Note that it is allowed to perform a partial repair on a contiguous group.

Key Insights

  • The potholes on the road appear in contiguous groups separated by smooth segments.
  • Repairing n potholes costs n+1. This means every operation has a fixed overhead cost of 1 in addition to the per-pothole cost.
  • For any contiguous group of potholes (of length L), if the remaining budget R allows a full operation (if R ≥ L+1), then it is optimal to repair the whole group; otherwise, one can repair a maximum of R-1 potholes on that group.
  • Since the overhead cost is paid per independent operation, it is more “budget‐efficient” to repair as many potholes as possible at once from a given contiguous block.
  • To maximize the number of potholes fixed, one should preferably “invest” the budget in groups that can yield more potholes fixed in one operation. Sorting the groups in descending order by their lengths is a useful greedy strategy.

Space and Time Complexity

Time Complexity: O(n + g log g)
  • O(n) to iterate and find all contiguous groups (g groups in the worst case g ≤ n).
  • O(g log g) to sort these groups. Space Complexity: O(g) for storing the lengths of contiguous pothole groups.

Solution

The solution involves the following steps:

  1. Traverse the road string to identify all contiguous groups of potholes (i.e. segments of consecutive "x").
  2. For each group, note its length.
  3. Sort the groups in descending order of their lengths. Since each repair operation has a cost overhead of 1, repairing a larger group is more cost‐efficient.
  4. Iterate over the sorted groups. For each group with length L:
    • If the remaining budget is at least L+1, repair the entire group (adding L fixed potholes and reducing the budget by L+1).
    • Otherwise, if the remaining budget R > 1, you can only repair R-1 potholes (cost = (R-1)+1 = R). Add these fixed potholes and exhaust the budget.
  5. Return the total number of potholes fixed.

Key “gotchas” include:

  • Always check that at least 2 budget units remain before performing an operation (because even fixing 1 pothole costs 2).
  • Repair isn’t forced to fix an entire group; partial fixes are allowed if the budget cannot cover the entire group.

Code Solutions

# Python solution with detailed comments

def maxPotholesFixed(road, budget):
    # List to store the lengths of contiguous pothole groups.
    groups = []
    count = 0
    
    # Traverse the road string to identify groups of consecutive 'x'
    for char in road:
        if char == 'x':
            count += 1
        else:
            if count > 0:
                groups.append(count)
                count = 0
    # Check if the road ends with a pothole group.
    if count > 0:
        groups.append(count)
    
    # Sort groups descending to prioritize long segments
    groups.sort(reverse=True)
    
    total_fixed = 0
    remaining_budget = budget
    
    for group in groups:
        # Check if at least 2 units are available to perform any repair
        if remaining_budget <= 1:
            break
        
        # If we have enough budget to fix the entire group
        if remaining_budget >= group + 1:
            total_fixed += group       # Fix all potholes in the group
            remaining_budget -= (group + 1)  # Deduct the cost (potholes fixed + overhead)
        else:
            # Otherwise, we can only fix a partial portion of this group:
            # You can fix at most (remaining_budget - 1) potholes because of the overhead cost of 1.
            fixed_here = remaining_budget - 1
            total_fixed += fixed_here
            remaining_budget = 0  # Budget is exhausted after this partial repair
    
    return total_fixed

# Example usage:
print(maxPotholesFixed("..xxxxx", 4))  # Expected output: 3
print(maxPotholesFixed("x.x.xxx...x", 14))  # Expected output: 6
← Back to All Questions