LeetCode 2188: Minimum Time to Finish the Race Solution

Master LeetCode problem 2188 (Minimum Time to Finish the Race), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2188. Minimum Time to Finish the Race

Hard

Array Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will iterate over all possible combinations of tire types and laps and keep track of the minimum time required to finish the race.

Create a 2D array dp of size (numLaps + 1) x tires.length to store the minimum time to finish i laps with each tire type.
Initialize the first row of dp with the time taken to finish the first lap with each tire type.
Iterate over laps starting from the second lap:
- For each lap, iterate over tire types and calculate the minimum time to finish the lap considering changing the tire or continuing with the current tire.
The answer will be the minimum time taken to finish numLaps laps with any tire type.

Time Complexity: The time complexity of this approach is O(numLaps * tires.length) as we are iterating over all possible combinations.

Space Complexity: The space complexity is O(numLaps * tires.length) for the dp array.

Solution Code

class Solution {
    public int minTimeToFinishRace(int[][] tires, int changeTime, int numLaps) {
        int n = tires.length;
        int[][] dp = new int[numLaps + 1][n];
        
        for (int i = 0; i < n; i++) {
            dp[1][i] = tires[i][0];
        }
        
        for (int lap = 2; lap <= numLaps; lap++) {
            for (int i = 0; i < n; i++) {
                dp[lap][i] = Math.min(dp[lap - 1][i] + tires[i][0], dp[lap - 1][(i + 1) % n] + changeTime + tires[i][0]);
            }
        }
        
        int minTime = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            minTime = Math.min(minTime, dp[numLaps][i]);
        }
        
        return minTime;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2188 (Minimum Time to Finish the Race)?

This page provides optimized solutions for LeetCode problem 2188 (Minimum Time to Finish the Race) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2188 (Minimum Time to Finish the Race)?

The time complexity for LeetCode 2188 (Minimum Time to Finish the Race) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2188 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2188 in Java, C++, or Python.

Back to LeetCode Solutions