Minimum Time to Finish the Race — Problem & Solution
Minimum Time to Finish the Race solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Time to Finish the Race is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A race has numLaps laps. Tire type i is tires[i] = [f, r]: on a fresh tire of this type the first lap takes f seconds, the second f * r, the third f * r^2, and so on — the x-th successive lap on the same tire takes f * r^(x - 1) seconds.
You start on any tire type you like. After any lap you may switch to a fresh tire of any type (including the type you are on), which costs changeTime seconds. Every type is available in unlimited supply.
Return the minimum total time to complete the race.
Example 1
Input: tires = [[1,2]], changeTime = 2, numLaps = 4
Output: 8
Explanation: Two laps (1 + 2), change (2), two laps (1 + 2): 8. Staying on one tire would cost 1 + 2 + 4 + 8 = 15.
Example 2
Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Example 3
Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Constraints
1 <= tires.length <= 10^5tires[i].length == 21 <= f, changeTime <= 10^52 <= r <= 10^51 <= numLaps <= 1000
Hints for Minimum Time to Finish the Race
Hint 1
Split the race into stints, each driven on one fresh tire. Let
best[k]be the cheapest way to driveklaps on a single fresh tire, over all types.Hint 2
Lap times at least double, so once a lap would take longer than
changeTime + f, changing to a fresh tire is better —best[k]is only needed for about 20 values ofk.Hint 3
Then
dp[i] = min over k of dp[i - k] + changeTime + best[k], withdp[0] = -changeTimeso the first stint pays no change.
How to solve Minimum Time to Finish the Race
Any strategy is a sequence of stints on fresh tires separated by changes. Precompute the best cost of a k-lap stint, which is only worth having for small k because lap times grow geometrically, and combine stints with a one-dimensional DP over laps.
Approach
- For each tire, walk its lap times
f, f*r, f*r^2, ...while a lap costs at mostchangeTime + f, accumulating the stint cost; keepbest[k] = minover tires. - Let
Kbe the largestkwith a finitebest[k]. - Set
dp[0] = -changeTime. Fori = 1..numLaps,dp[i] = min(dp[i - k] + changeTime + best[k])over1 <= k <= min(i, K). - Return
dp[numLaps].
Why it works
If the x-th lap of a stint costs more than changeTime + f, replacing it (and everything after it) by a change plus a fresh tire of the same type is strictly cheaper, so optimal stints never contain such a lap, and dropping those best[k] values loses nothing. Since r >= 2, the lap time passes changeTime + f <= 2 * 10^5 within about 18 laps. The DP then tries every length for the final stint, which covers every sequence of stints.
Complexity
- Time —
O(T log C + numLaps * K) - Space —
O(numLaps)
Pitfalls
f * r^(x - 1)overflows quickly — stop the walk before multiplying past the cap, and use 64-bit for the lap time.- The first stint has no change before it; the
dp[0] = -changeTimetrick handles that. - Switching to a fresh tire of the same type is allowed and is often the best move.
Reference solution
Python
from typing import List
def minimumFinishTime(tires: List[List[int]], changeTime: int, numLaps: int) -> int:
INF = float('inf')
best = [INF] * (numLaps + 1) # best[k]: k laps on one fresh tire
top = 0
for f, r in tires:
lap, total, k = f, 0, 1
while k <= numLaps and lap <= changeTime + f:
total += lap
best[k] = min(best[k], total)
top = max(top, k)
lap *= r
k += 1
dp = [0] * (numLaps + 1)
dp[0] = -changeTime # the first stint needs no change
for i in range(1, numLaps + 1):
dp[i] = min(dp[i - k] + changeTime + best[k] for k in range(1, min(i, top) + 1))
return dp[numLaps]Java
public static int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
long INF = Long.MAX_VALUE / 4;
long[] best = new long[numLaps + 1]; // best[k]: k laps on one fresh tire
Arrays.fill(best, INF);
int top = 0;
for (int[] tire : tires) {
long f = tire[0], r = tire[1];
long lap = f, total = 0;
for (int k = 1; k <= numLaps && lap <= changeTime + f; k++) {
total += lap;
best[k] = Math.min(best[k], total);
top = Math.max(top, k);
lap *= r;
}
}
long[] dp = new long[numLaps + 1];
dp[0] = -changeTime; // the first stint needs no change
for (int i = 1; i <= numLaps; i++) {
dp[i] = INF;
for (int k = 1; k <= Math.min(i, top); k++) dp[i] = Math.min(dp[i], dp[i - k] + changeTime + best[k]);
}
return (int) dp[numLaps];
}C++
int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
const long long INF = LLONG_MAX / 4;
vector<long long> best(numLaps + 1, INF); // best[k]: k laps on one fresh tire
int top = 0;
for (auto& tire : tires) {
long long f = tire[0], r = tire[1];
long long lap = f, total = 0;
for (int k = 1; k <= numLaps && lap <= changeTime + f; k++) {
total += lap;
best[k] = min(best[k], total);
top = max(top, k);
lap *= r;
}
}
vector<long long> dp(numLaps + 1, INF);
dp[0] = -changeTime; // the first stint needs no change
for (int i = 1; i <= numLaps; i++) {
for (int k = 1; k <= min(i, top); k++) dp[i] = min(dp[i], dp[i - k] + changeTime + best[k]);
}
return (int) dp[numLaps];
}JavaScript
var minimumFinishTime = function(tires, changeTime, numLaps) {
var INF = 1e18;
var best = []; // best[k]: k laps on one fresh tire
for (var z = 0; z <= numLaps; z++) best.push(INF);
var top = 0;
for (var t = 0; t < tires.length; t++) {
var f = tires[t][0], r = tires[t][1];
var lap = f, total = 0;
for (var k = 1; k <= numLaps && lap <= changeTime + f; k++) {
total += lap;
if (total < best[k]) best[k] = total;
if (k > top) top = k;
lap *= r;
}
}
var dp = [-changeTime]; // the first stint needs no change
for (var i = 1; i <= numLaps; i++) {
var cur = INF;
for (var j = 1; j <= Math.min(i, top); j++) {
var cand = dp[i - j] + changeTime + best[j];
if (cand < cur) cur = cand;
}
dp.push(cur);
}
return dp[numLaps];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming