Minimum Time to Finish the Race

Hard

#1993Time: O(T*C + 2^numLaps)Space: O(numLaps)

Patterns

Data structures

Prompt

You are given a 0-indexed 2D integer array tires where tires[i] = [f_i, r_i] indicates that the i^th tire can finish its x^th successive lap in f_i * r_i^(x-1) seconds.

For example, if f_i = 3 and r_i = 2, then the tire would finish its 1^st lap in 3 seconds, its 2^nd lap in 3 * 2 = 6 seconds, its 3^rd lap in 3 * 2² = 12 seconds, etc.

You are also given an integer changeTime and an integer numLaps.

The race consists of numLaps laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait changeTime seconds.

Return the minimum time to finish the race.

Example 1:

Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Explanation: 
Lap 1: Start with tire 0 and finish the lap in 2 seconds.
Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the race is 21 seconds.

Example 2:

Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Explanation: 
Lap 1: Start with tire 1 and finish the lap in 2 seconds.
Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the race is 25 seconds.

Constraints:

1 <= tires.length <= 10⁵
tires[i].length == 2
1 <= f_i, changeTime <= 10⁵
2 <= r_i <= 10⁵
1 <= numLaps <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a recursive function to explore all possible ways to finish the race. For a given number of laps n, it tries all possible lengths k for the first "stint" (a sequence of laps on a single tire). It calculates the time for this stint of k laps, adds the changeTime, and recursively calls the function for the remaining n-k laps. The base case is when there are no laps left. This method explores many redundant subproblems, leading to very high time complexity.

Algorithm

Precompute an array bestStint where bestStint[k] stores the minimum time to complete k consecutive laps using any single tire. This is a necessary pre-step for any recursive or dynamic programming solution.
Define a recursive function, say solve(lapsRemaining), that calculates the minimum time to finish the given number of laps.
Base Case: If lapsRemaining is 0, the time taken is 0. Return 0.
Recursive Step: For n laps remaining, explore all possibilities for the next stint:
- Iterate k from 1 to n.
- The cost for a stint of k laps followed by a change is bestStint[k] + changeTime + solve(n - k).
- The cost for completing all n laps in a single stint (no change) is bestStint[n].
- The function returns the minimum of all these possibilities.
The initial call is solve(numLaps), but the logic needs to be slightly adjusted to handle the fact that the first stint does not incur a changeTime.
A clearer recursive formulation is solve(n) = min(bestStint[n], min_{1 <= k < n} (bestStint[k] + changeTime + solve(n-k))).

Walkthrough

The brute-force recursive approach directly translates the problem's choices into a recursive structure. We define a function solve(n) that computes the minimum time for n laps. To compute solve(n), we consider two main scenarios:

Single Stint: We complete all n laps using a single tire without any changes. The time for this is the minimum time to run n consecutive laps, which we can precompute as bestStint[n].
Multiple Stints: We complete the first stint of k laps (where 1 <= k < n), then pay the changeTime, and then recursively find the minimum time for the remaining n-k laps. We try this for all possible values of k.

The final answer for solve(n) is the minimum over all these possibilities. This method is simple to understand but computationally expensive because solve(m) for a given m will be called many times with the same input, leading to an exponential number of total calls.

1// Note: This is a conceptual example. A pure recursive solution2// would be too slow. It's presented to illustrate the concept3// before optimizing with memoization or DP.4class Solution {5    long[] bestStint;6    int changeTime;7 8    // Precomputation of bestStint would be done here...9 10    private long solve(int laps) {11        if (laps == 0) {12            return 0;13        }14 15        // Option 1: Run all 'laps' in one stint16        long minTime = (laps < bestStint.length) ? bestStint[laps] : Long.MAX_VALUE;17 18        // Option 2: Run k laps, change, then solve for laps-k19        for (int k = 1; k < laps; k++) {20            if (k < bestStint.length && bestStint[k] != Long.MAX_VALUE) {21                long recursiveResult = solve(laps - k);22                if (recursiveResult != Long.MAX_VALUE) {23                    long time = bestStint[k] + this.changeTime + recursiveResult;24                    minTime = Math.min(minTime, time);25                }26            }27        }28        return minTime;29    }30}

Complexity

Time

O(T*C + 2^numLaps)

Space

O(numLaps)

Trade-offs

Pros

Simple to conceptualize and implement.
Directly models the decision-making process described in the problem.

Cons

Extremely inefficient due to exponential time complexity.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Calculates the same subproblems multiple times, leading to a lot of wasted computation.

This approach solves the problem efficiently by using dynamic programming. It avoids the redundant computations of the recursive approach by storing the results of subproblems. We define dp[i] as the minimum time required to complete i laps. We compute dp[i] for i = 1, 2, ..., numLaps.

To find dp[i], we consider all possible lengths of the final stint of laps. If the final stint has length k, it means we previously completed i-k laps in an optimal time dp[i-k], then paid a changeTime cost, and finally ran the last k laps. The cost for these last k laps is precomputed as bestStint[k]. By iterating through all possible split points, we find the minimum time for i laps.

Algorithm

Precomputation:
1. Create an array bestStint of size numLaps + 1, initialized with a large value. This array will store the minimum time to complete k consecutive laps on a single tire.
2. Iterate through each tire [f, r] in the input tires.
3. For each tire, calculate the cumulative time for k=1, 2, ... consecutive laps. Update bestStint[k] with the minimum time found.
4. We can optimize this by stopping the calculation for a tire once a single lap's time becomes excessively large (e.g., greater than changeTime + f), as it would always be better to switch tires.
Dynamic Programming:
1. Create a DP array dp of size numLaps + 1, initialized with a large value. Set dp[0] = 0.
2. Iterate i from 1 to numLaps to compute dp[i].
3. For each i, consider two possibilities to achieve the minimum time: a. Complete all i laps in a single stint. The time is bestStint[i]. So, initialize dp[i] = bestStint[i]. b. Complete the race in multiple stints. The last stint has some length k (1 <= k < i). This means we completed i-k laps, paid changeTime, and then ran the last k laps. The time is dp[i-k] + changeTime + bestStint[k]. We check this for all possible previous completion points j = i-k.
4. The DP transition is: dp[i] = min(dp[i], dp[j] + changeTime + bestStint[i-j]) for 1 <= j < i.
5. The final answer is dp[numLaps].

Walkthrough

The core of this method is to build up the solution for n laps from the solutions for fewer laps. Let dp[i] be the minimum time to finish i laps.

First, we precompute an array bestStint where bestStint[k] is the minimum time to run k consecutive laps using any single tire. This is done by iterating through all available tires and simulating their performance for an increasing number of laps. Since lap times grow exponentially (r >= 2), a single tire is only optimal for a relatively small number of consecutive laps before it's better to switch. We can prune the simulation for a tire once its next lap time exceeds changeTime + f (cost to switch to a fresh tire of the same type).

After precomputation, we build the dp table:

dp[0] = 0 (0 laps take 0 time).
For i from 1 to numLaps, dp[i] is the minimum of:
1. bestStint[i]: The time to run all i laps in one go, without changing tires.
2. dp[j] + changeTime + bestStint[i-j] for all 1 <= j < i: The time to finish j laps optimally, pay the changeTime, and then run the remaining i-j laps in a single stint.

By filling the dp table this way, dp[numLaps] will hold the minimum time for the entire race.

1import java.util.Arrays;2 3class Solution {4    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {5        // bestStint[k] = min time to run k consecutive laps with one tire6        long[] bestStint = new long[numLaps + 1];7        Arrays.fill(bestStint, Long.MAX_VALUE);8 9        // Precompute bestStint array10        for (int[] tire : tires) {11            long f = tire[0];12            long r = tire[1];13            long currentLapTime = f;14            long totalStintTime = 0;15 16            for (int k = 1; k <= numLaps; k++) {17                totalStintTime += currentLapTime;18                19                // A very large total time is not useful and can overflow.20                // The max possible answer is roughly numLaps * (max_f + changeTime) ~ 2*10^8.21                if (totalStintTime > 2_000_000_000L) { 22                    break;23                }24 25                bestStint[k] = Math.min(bestStint[k], totalStintTime);26                27                currentLapTime *= r;28                // Optimization: if the next lap is more expensive than changing + one lap with this same tire type29                if (currentLapTime > changeTime + f) {30                    break;31                }32            }33        }34 35        // dp[i] = min time to finish i laps36        long[] dp = new long[numLaps + 1];37        Arrays.fill(dp, Long.MAX_VALUE);38        dp[0] = 0;39 40        for (int i = 1; i <= numLaps; i++) {41            // Option 1: Run all i laps in one stint42            if (i < bestStint.length) {43                dp[i] = bestStint[i];44            }45 46            // Option 2: Run j laps, change, then run i-j laps in the last stint47            for (int j = 1; j < i; j++) {48                if (dp[j] != Long.MAX_VALUE && (i - j) < bestStint.length && bestStint[i - j] != Long.MAX_VALUE) {49                    dp[i] = Math.min(dp[i], dp[j] + changeTime + bestStint[i - j]);50                }51            }52        }53 54        return (int) dp[numLaps];55    }56}

Complexity

Time

O(T * C + numLaps^2)

Space

O(numLaps)

Trade-offs

Pros

Guarantees finding the optimal solution.
Efficient enough to pass the given constraints.
Systematically builds the solution, avoiding re-computation.

Cons

The O(numLaps^2) complexity might be too slow if the numLaps constraint were significantly larger.

Solutions

Solution

1class Solution {2public3  int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {4    final int inf = 1 << 30;5    int[] cost = new int[18];6    Arrays.fill(cost, inf);7    for (int[] e : tires) {8      int f = e[0], r = e[1];9      int s = 0, t = f;10      for (int i = 1; t <= changeTime + f; ++i) {11        s += t;12        cost[i] = Math.min(cost[i], s);13        t *= r;14      }15    }16    int[] f = new int[numLaps + 1];17    Arrays.fill(f, inf);18    f[0] = -changeTime;19    for (int i = 1; i <= numLaps; ++i) {20      for (int j = 1; j < Math.min(18, i + 1); ++j) {21        f[i] = Math.min(f[i], f[i - j] + cost[j]);22      }23      f[i] += changeTime;24    }25    return f[numLaps];26  }27}

1class Solution {2public:3  int minimumFinishTime(vector<vector<int>> &tires, int changeTime,4                        int numLaps) {5    int cost[18];6    memset(cost, 0x3f, sizeof(cost));7    for (auto &e : tires) {8      int f = e[0], r = e[1];9      int s = 0;10      long long t = f;11      for (int i = 1; t <= changeTime + f; ++i) {12        s += t;13        cost[i] = min(cost[i], s);14        t *= r;15      }16    }17    int f[numLaps + 1];18    memset(f, 0x3f, sizeof(f));19    f[0] = -changeTime;20    for (int i = 1; i <= numLaps; ++i) {21      for (int j = 1; j < min(18, i + 1); ++j) {22        f[i] = min(f[i], f[i - j] + cost[j]);23      }24      f[i] += changeTime;25    }26    return f[numLaps];27  }28};

1class Solution:2    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int: cost = [inf] * 18 for f, r in tires: i, s, t = 1, 0, f while t <= changeTime + f: s += t cost[i] = min(cost[i], s) t *= r i += 1 f = [inf] * (numLaps + 1) f[0] = - changeTime for i in range(1, numLaps + 1): for j in range(1, min(18, i + 1)): f[i] = min(f[i], f[i - j] + cost[j]) f[i] += changeTime return f[numLaps]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem