Formula 1 Last Lap Improvement

Overview

The goal is to identify which driver improved their performance the most on the final lap compared to their average performance in all preceding laps.

For every driver, we must calculate:

1. The sum of all lap times except the last one.
2. The average of those times.
3. The difference between that average and the last lap time.

The problem also specifies a tie-breaking rule: if multiple drivers achieve the same maximum improvement, we return the driver whose name is lexicographically first (alphabetically first).

Brute Force

The brute force approach involves iterating through the list of drivers, and for each driver, manually iterating through their lap times to calculate the sum and average. We store the improvements in a list or dictionary and then perform a second pass to find the maximum value and handle the lexicographical tie-break.

def getBestImprover(drivers: list[str], lapTimes: list[list[float]]) -> str:
    improvements = []
    
    for i in range(len(drivers)):
        name = drivers[i]
        times = lapTimes[i]
        
        # Calculate average of all laps except the last one
        prev_laps = times[:-1]
        sum_prev = 0
        for t in prev_laps:
            sum_prev += t
        
        avg_prev = sum_prev / len(prev_laps)
        last_lap = times[-1]
        improvement = avg_prev - last_lap
        
        improvements.append((improvement, name))
        
    # Find the best improvement
    # We sort by improvement descending, then name ascending
    # Python's sort is stable, but we can use a custom key
    best_driver = None
    max_imp = -float('inf')
    
    for imp, name in improvements:
        if imp > max_imp:
            max_imp = imp
            best_driver = name
        elif imp == max_imp:
            if best_driver is None or name < best_driver:
                best_driver = name
                
    return best_driver

Time complexity: O(N * M) — Where N is the number of drivers and M is the number of laps; we visit every lap time once. Space complexity: O(N) — We store the improvement value and name for each driver.

Optimal / Best Approach

The optimal approach performs the calculation in a single pass without storing all intermediate improvements. We maintain two variables: best_driver and max_improvement. As we calculate the improvement for the current driver, we compare it to our current maximum.

To handle the lexicographical requirement efficiently, we update the best_driver if:

1. The current improvement is strictly greater than the max_improvement.
2. The current improvement is equal to the max_improvement AND the current name is alphabetically smaller than the best_driver.

def getBestImprover(drivers: list[str], lapTimes: list[list[float]]) -> str:
    best_driver = ""
    max_improvement = -float('inf')
    
    for i in range(len(drivers)):
        name = drivers[i]
        times = lapTimes[i]
        
        # The number of laps before the last one
        n_prev = len(times) - 1
        
        # Calculate average: (Total Sum - Last Lap) / (Total Laps - 1)
        # Using Python's sum() is efficient and idiomatic
        avg_prev = (sum(times) - times[-1]) / n_prev
        improvement = avg_prev - times[-1]
        
        # Check if this driver is better than the current leader
        if improvement > max_improvement:
            max_improvement = improvement
            best_driver = name
        elif improvement == max_improvement:
            # Tie-break: Lexicographical order
            if name < best_driver:
                best_driver = name
                
    return best_driver

Time complexity: O(N * M) — We must touch every lap time at least once to calculate the average. Space complexity: O(1) — We only store a few variables (max_improvement, best_driver) regardless of the input size, excluding the input storage itself.

Edge Cases

• Tie-breaks: The logic name < best_driver correctly handles the case where two drivers have identical improvement scores (e.g., Example 4).
• Negative Improvement: If a driver's last lap is slower than their average, the improvement will be negative. The initial max_improvement is set to -float('inf') to ensure we capture even the "least bad" improvement if all drivers slowed down.
• Large Lap Counts: Using sum(times) - times[-1] is slightly more efficient than slicing times[:-1] as it avoids creating a new list in memory.

Fast