Minimum Time to Finish the Race - Solution & Explanation

Problem Overview: You have multiple tire types where each lap gets slower due to degradation. After any lap you can change tires with a fixed changeTime. The goal is to finish numLaps with the minimum total time by deciding when to continue with the same tire or perform a tire change.

Approach 1: Greedy + Brute Force for Small Laps (O(t * n^2) time, O(n) space)

The naive idea is to simulate how long a tire performs if you keep using it for consecutive laps. For each tire with base time f and degradation factor r, lap times grow as f, f*r, f*r^2.... If the next lap becomes slower than starting fresh after a tire change (changeTime + f), continuing is pointless. Precompute cumulative times for every tire while it remains beneficial. Then try building the race lap-by-lap using brute force: for every lap count i, test all possible previous segments of consecutive laps. This approach directly models the decision process but becomes expensive when numLaps grows large.

Approach 2: Dynamic Programming with Precomputation (O(t * k + n * k) time, O(n) space)

The key observation: no tire is useful for many consecutive laps because degradation grows exponentially. For each tire, simulate consecutive laps until the next lap exceeds changeTime + f. Track the best possible time to complete exactly k consecutive laps without a tire change. Because growth is exponential, k stays small (usually ≤ 18).

Once these values are precomputed, the problem becomes classic dynamic programming. Let dp[i] be the minimum time to finish i laps. For every possible consecutive segment length k, update:

dp[i] = min(dp[i], dp[i-k] + best[k] + changeTime)

The extra changeTime represents switching tires before the new segment. Handle the first segment separately so it does not pay the initial change cost. Precomputation limits the inner loop to a small constant, turning a potentially quadratic search into a near linear solution.

This method combines insights from array processing and dynamic programming. Instead of exploring every tire choice at every lap, it compresses all tire behavior into the best possible segment times.

Recommended for interviews: Dynamic Programming with precomputation. Interviewers expect you to notice that tire degradation grows exponentially, which bounds the number of useful consecutive laps. Demonstrating the brute-force idea shows understanding of the decision space, but the optimized DP proves you can reduce the search space and build an efficient solution.