Problem

You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the ith tire can finish its xth successive lap in `fi

  • ri(x-1)` seconds.

    • For example, if fi = 3 and ri = 2, then the tire would finish its 1st lap in 3 seconds, its 2nd lap in 3 * 2 = 6 seconds, its 3rd lap in 3 * 22 = 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 theminimum time to finish the race.

Examples

Example 1

1
2
3
4
5
6
7
8
9

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Solution

Method 1 – Dynamic Programming with Preprocessing

Intuition

For each tire, the lap time increases exponentially. It’s optimal to use a tire for several consecutive laps until it’s better to change. Precompute the minimum time to finish k consecutive laps with any tire, then use DP to find the minimum total time for numLaps.

Approach

  1. For each tire, precompute the minimum time to run k consecutive laps (without changing tires), up to a reasonable limit (when lap time exceeds changeTime + best first lap).
  2. For each k, keep the minimum time among all tires.
  3. Use DP: dp[i] = minimum time to finish i laps.
  4. For each i, try all possible k (consecutive laps) and update dp[i] = min(dp[i], dp[i-k] + minTime[k] + changeTime).
  5. The answer is dp[numLaps] minus changeTime (no change after last lap).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        const int INF = 1e9;
        vector<int> minTime(numLaps+1, INF);
        for (auto& t : tires) {
            int f = t[0], r = t[1];
            long long time = 0, curr = f;
            for (int k = 1; k <= numLaps && curr <= f + changeTime; ++k) {
                time += curr;
                minTime[k] = min(minTime[k], (int)time);
                curr *= r;
            }
        }
        vector<int> dp(numLaps+1, INF);
        dp[0] = 0;
        for (int i = 1; i <= numLaps; ++i) {
            for (int k = 1; k <= i; ++k) {
                if (minTime[k] < INF)
                    dp[i] = min(dp[i], dp[i-k] + minTime[k] + changeTime);
            }
        }
        return dp[numLaps] - changeTime;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func minimumFinishTime(tires [][]int, changeTime, numLaps int) int {
    const INF = 1e9
    minTime := make([]int, numLaps+1)
    for i := range minTime {
        minTime[i] = INF
    }
    for _, t := range tires {
        f, r := t[0], t[1]
        time, curr := 0, f
        for k := 1; k <= numLaps && curr <= f+changeTime; k++ {
            time += curr
            if time < minTime[k] {
                minTime[k] = time
            }
            curr *= r
        }
    }
    dp := make([]int, numLaps+1)
    for i := range dp {
        dp[i] = INF
    }
    dp[0] = 0
    for i := 1; i <= numLaps; i++ {
        for k := 1; k <= i; k++ {
            if minTime[k] < INF && dp[i-k]+minTime[k]+changeTime < dp[i] {
                dp[i] = dp[i-k]+minTime[k]+changeTime
            }
        }
    }
    return dp[numLaps] - changeTime
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
        int INF = (int)1e9;
        int[] minTime = new int[numLaps+1];
        Arrays.fill(minTime, INF);
        for (int[] t : tires) {
            int f = t[0], r = t[1];
            long time = 0, curr = f;
            for (int k = 1; k <= numLaps && curr <= f + changeTime; k++) {
                time += curr;
                minTime[k] = Math.min(minTime[k], (int)time);
                curr *= r;
            }
        }
        int[] dp = new int[numLaps+1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 1; i <= numLaps; i++) {
            for (int k = 1; k <= i; k++) {
                if (minTime[k] < INF)
                    dp[i] = Math.min(dp[i], dp[i-k] + minTime[k] + changeTime);
            }
        }
        return dp[numLaps] - changeTime;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun minimumFinishTime(tires: Array<IntArray>, changeTime: Int, numLaps: Int): Int {
        val INF = 1e9.toInt()
        val minTime = IntArray(numLaps+1) { INF }
        for (t in tires) {
            var f = t[0]
            var r = t[1]
            var time = 0L
            var curr = f
            for (k in 1..numLaps) {
                if (curr > f + changeTime) break
                time += curr
                minTime[k] = minOf(minTime[k], time.toInt())
                curr *= r
            }
        }
        val dp = IntArray(numLaps+1) { INF }
        dp[0] = 0
        for (i in 1..numLaps) {
            for (k in 1..i) {
                if (minTime[k] < INF)
                    dp[i] = minOf(dp[i], dp[i-k] + minTime[k] + changeTime)
            }
        }
        return dp[numLaps] - changeTime
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def minimumFinishTime(self, tires: list[list[int]], changeTime: int, numLaps: int) -> int:
        INF = int(1e9)
        minTime = [INF] * (numLaps+1)
        for f, r in tires:
            time, curr = 0, f
            for k in range(1, numLaps+1):
                if curr > f + changeTime:
                    break
                time += curr
                minTime[k] = min(minTime[k], time)
                curr *= r
        dp = [INF] * (numLaps+1)
        dp[0] = 0
        for i in range(1, numLaps+1):
            for k in range(1, i+1):
                if minTime[k] < INF:
                    dp[i] = min(dp[i], dp[i-k] + minTime[k] + changeTime)
        return dp[numLaps] - changeTime
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn minimum_finish_time(tires: Vec<Vec<i32>>, change_time: i32, num_laps: i32) -> i32 {
        let inf = 1_000_000_000;
        let num_laps = num_laps as usize;
        let mut min_time = vec![inf; num_laps+1];
        for t in tires.iter() {
            let (f, r) = (t[0], t[1]);
            let mut time = 0;
            let mut curr = f;
            for k in 1..=num_laps {
                if curr > f + change_time { break; }
                time += curr;
                min_time[k] = min_time[k].min(time);
                curr *= r;
            }
        }
        let mut dp = vec![inf; num_laps+1];
        dp[0] = 0;
        for i in 1..=num_laps {
            for k in 1..=i {
                if min_time[k] < inf {
                    dp[i] = dp[i].min(dp[i-k] + min_time[k] + change_time);
                }
            }
        }
        dp[num_laps] - change_time
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    minimumFinishTime(tires: number[][], changeTime: number, numLaps: number): number {
        const INF = 1e9;
        const minTime = Array(numLaps+1).fill(INF);
        for (const [f, r] of tires) {
            let time = 0, curr = f;
            for (let k = 1; k <= numLaps && curr <= f + changeTime; k++) {
                time += curr;
                minTime[k] = Math.min(minTime[k], time);
                curr *= r;
            }
        }
        const dp = Array(numLaps+1).fill(INF);
        dp[0] = 0;
        for (let i = 1; i <= numLaps; i++) {
            for (let k = 1; k <= i; k++) {
                if (minTime[k] < INF)
                    dp[i] = Math.min(dp[i], dp[i-k] + minTime[k] + changeTime);
            }
        }
        return dp[numLaps] - changeTime;
    }
}

Complexity

  • ⏰ Time complexity: O(numLaps^2 + tires.length * numLaps), due to DP and preprocessing.
  • 🧺 Space complexity: O(numLaps), for DP and minTime arrays.