#2188
Minimum Time to Finish the Race
HardArrayDynamic ProgrammingDynamic ProgrammingGreedy Algorithms
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n * m) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n * m)Space O(n)
We can precompute the minimum time to complete laps without changing tires and use dynamic programming to efficiently calculate the total time for numLaps.
⚙️
Algorithm
3 steps- 1Step 1: Precompute the minimum time for completing up to a certain number of laps with each tire without changing.
- 2Step 2: Use dynamic programming to combine these precomputed values with the changeTime to find the optimal configuration for numLaps.
- 3Step 3: Iterate through the precomputed values to find the minimum total time.
solution.py20 lines
1def minTimeToFinishRace(tires, changeTime, numLaps):
2 max_laps = 0
3 min_time = [float('inf')] * (numLaps + 1)
4 for f, r in tires:
5 time = 0
6 lap_time = f
7 for lap in range(1, numLaps + 1):
8 time += lap_time
9 if time > min_time[lap]:
10 break
11 min_time[lap] = time
12 lap_time *= r
13 max_laps = lap
14 dp = [float('inf')] * (numLaps + 1)
15 dp[0] = 0
16 for laps in range(1, numLaps + 1):
17 for k in range(1, max_laps + 1):
18 if laps - k >= 0:
19 dp[laps] = min(dp[laps], dp[laps - k] + min_time[k] + changeTime)
20 return dp[numLaps]ℹ
Complexity note: The time complexity is O(n * m) where n is the number of tires and m is the number of laps, as we compute the minimum time for each tire and each lap.
- 1Precomputing values can significantly reduce time complexity.
- 2Dynamic programming helps in breaking down the problem into manageable subproblems.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.