2188. Minimum Time to Finish the Race LeetCode Solution
In this guide, you will get 2188. Minimum Time to Finish the Race LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Finish the Race problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Time to Finish the Race solution in C++
- Minimum Time to Finish the Race solution in Java
- Minimum Time to Finish the Race solution in Python
- Additional Resources
Problem Statement of Minimum Time to Finish the Race
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 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 <= 105
tires[i].length == 2
1 <= fi, changeTime <= 105
2 <= ri <= 105
1 <= numLaps <= 1000
Complexity Analysis
- Time Complexity: O(|\texttt{tires}| + \texttt{numLaps}^2)
- Space Complexity: O(\texttt{numLaps})
2188. Minimum Time to Finish the Race LeetCode Solution in C++
class Solution {
public:
int minimumFinishTime(vector<vector<int>>& tires, int changeTime,
int numLaps) {
// singleTire[i] := the minimum time to finish i laps without changing tire
vector<int> singleTire(numLaps + 1, INT_MAX / 2);
// dp[i] := the minimum time to finish i laps
vector<int> dp(numLaps + 1, INT_MAX / 2);
for (int i = 0; i < tires.size(); ++i) {
const int f = tires[i][0];
const int r = tires[i][1];
int sumSecs = 0;
int rPower = 1;
for (int j = 1; j <= numLaps; ++j) {
// the time to use the same tire for the next lap >=
// the time to change a new tire + f
if ((long)f * rPower >= changeTime + f)
break;
sumSecs += f * rPower;
rPower *= r;
singleTire[j] = min(singleTire[j], sumSecs);
}
}
dp[0] = 0;
for (int i = 1; i <= numLaps; ++i)
for (int j = 1; j <= i; ++j)
dp[i] = min(dp[i], dp[i - j] + changeTime + singleTire[j]);
return dp[numLaps] - changeTime;
}
};
/* code provided by PROGIEZ */2188. Minimum Time to Finish the Race LeetCode Solution in Java
class Solution {
public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
// singleTire[i] := the minimum time to finish i laps without changing tire
int[] singleTire = new int[numLaps + 1];
// dp[i] := the minimum time to finish i laps
int[] dp = new int[numLaps + 1];
Arrays.fill(singleTire, Integer.MAX_VALUE / 2);
Arrays.fill(dp, Integer.MAX_VALUE / 2);
for (int i = 0; i < tires.length; ++i) {
final int f = tires[i][0];
final int r = tires[i][1];
int sumSecs = 0;
int rPower = 1;
for (int j = 1; j <= numLaps; ++j) {
// the time to use the same tire for the next lap >=
// the time to change a new tire + f
if ((long) f * rPower >= changeTime + f)
break;
sumSecs += f * rPower;
rPower *= r;
singleTire[j] = Math.min(singleTire[j], sumSecs);
}
}
dp[0] = 0;
for (int i = 1; i <= numLaps; ++i)
for (int j = 1; j <= i; ++j)
dp[i] = Math.min(dp[i], dp[i - j] + changeTime + singleTire[j]);
return dp[numLaps] - changeTime;
}
}
// code provided by PROGIEZ2188. Minimum Time to Finish the Race LeetCode Solution in Python
class Solution:
def minimumFinishTime(
self,
tires: list[list[int]],
changeTime: int,
numLaps: int,
) -> int:
# singleTire[i] := the minimum time to finish i laps without changing tire
singleTire = [math.inf] * (numLaps + 1)
# dp[i] := the minimum time to finish i laps
dp = [math.inf] * (numLaps + 1)
for i, (f, r) in enumerate(tires):
sumSecs = 0
rPower = 1
for j in range(1, numLaps + 1):
# the time to use the same tire for the next lap >=
# the time to change a new tire + f
if f * rPower >= changeTime + f:
break
sumSecs += f * rPower
rPower *= r
singleTire[j] = min(singleTire[j], sumSecs)
dp[0] = 0
for i in range(1, numLaps + 1):
for j in range(1, i + 1):
dp[i] = min(dp[i], dp[i - j] + changeTime + singleTire[j])
return dp[numLaps] - changeTime
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.