Minimum Time to Finish the Race

Hard
1446.

Minimum Time to Finish the Race

Minimum Time to Finish the Race is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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^5
  • tires[i].length == 2
  • 1 <= f, changeTime <= 10^5
  • 2 <= r <= 10^5
  • 1 <= numLaps <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} tires
 * @param {number} changeTime
 * @param {number} numLaps
 * @return {number}
 */
var minimumFinishTime = function(tires, changeTime, numLaps) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • tires[i].length == 2
  • 1 <= f, changeTime <= 10^5
  • 2 <= r <= 10^5
  • 1 <= numLaps <= 1000

Hints for Minimum Time to Finish the Race

  1. Hint 1

    Split the race into stints, each driven on one fresh tire. Let best[k] be the cheapest way to drive k laps on a single fresh tire, over all types.

  2. 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 of k.

  3. Hint 3

    Then dp[i] = min over k of dp[i - k] + changeTime + best[k], with dp[0] = -changeTime so 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

  1. For each tire, walk its lap times f, f*r, f*r^2, ... while a lap costs at most changeTime + f, accumulating the stint cost; keep best[k] = min over tires.
  2. Let K be the largest k with a finite best[k].
  3. Set dp[0] = -changeTime. For i = 1..numLaps, dp[i] = min(dp[i - k] + changeTime + best[k]) over 1 <= k <= min(i, K).
  4. 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] = -changeTime trick 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