LeetCode 2188 - Minimum Time to Finish the Race

The problem asks us to find the minimum total time to complete a race of numLaps laps using a collection of tires, where each tire has two parameters: a base lap time fi and a multiplier ri.

leetcodehardarraydynamic-programming

LeetCode Problem 2188

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find the minimum total time to complete a race of numLaps laps using a collection of tires, where each tire has two parameters: a base lap time fi and a multiplier ri. The time it takes a tire to complete successive laps grows geometrically according to the formula fi * ri^(x-1) for the xth lap. After each lap, you can either continue with the same tire (which will become slower on the next lap due to the multiplier) or switch to a fresh tire, paying changeTime seconds for the switch. You can pick any tire to start and have unlimited supply of each tire type.

The inputs are:

  • tires: a 2D list of integers where each sublist [fi, ri] describes a tire's lap performance.
  • changeTime: integer seconds required to switch tires.
  • numLaps: total number of laps in the race.

The expected output is a single integer representing the minimum time to finish all laps, considering optimal tire selection and switching.

Constraints reveal important properties:

  • 1 <= tires.length <= 10^5 indicates there may be many tire types.
  • 1 <= fi, changeTime <= 10^5 and 2 <= ri <= 10^5 indicate that lap times and multipliers can be large.
  • 1 <= numLaps <= 1000 is relatively small, which suggests we may precompute or use DP over the number of laps.

Edge cases include extremely high multipliers that make continuing with the same tire extremely costly, or very high changeTime that discourages frequent tire changes. Tires with ri = 1 would be special since continuing on the same tire does not increase lap time.

Approaches

The brute-force approach would try every possible sequence of tire choices for all numLaps laps. For each lap, you could either continue with the current tire or switch to any other tire. This guarantees the correct answer, but the number of sequences grows exponentially with numLaps and the number of tires, making it infeasible.

The key insight is that the cost of using a tire for consecutive laps grows geometrically. Therefore, we can precompute for each tire the minimal time to complete up to k consecutive laps without changing, stopping when continuing becomes more expensive than changing. After this, the problem reduces to a classic dynamic programming problem over laps, where for each lap we decide the optimal number of consecutive laps to perform with a fresh tire.

This allows us to handle large tires arrays efficiently by focusing only on the "best sequence" of consecutive laps and then using DP to compute the minimum total time.

Approach Time Complexity Space Complexity Notes
Brute Force O((#tires)^numLaps) O(numLaps) Tries all sequences of tire choices; infeasible
Optimal O(numLaps * maxConsecLaps + #tires * maxConsecLaps) O(numLaps + maxConsecLaps) Precompute minimal consecutive lap times for each tire and use DP over laps

Algorithm Walkthrough

  1. Precompute minimal consecutive lap times: For each tire [fi, ri], compute cumulative lap times for consecutive laps until the next lap would exceed fi + changeTime (since switching is cheaper). Store the minimal time for 1 lap, 2 laps, … up to maxConsecLaps.
  2. Build a global minimal consecutive lap table: For each k consecutive laps, find the minimum time among all tires to perform those laps consecutively. This captures the best "segment" you can do without changing.
  3. Dynamic Programming over laps: Initialize a DP array dp[i] representing the minimum time to complete i laps. Set dp[0] = 0. For each lap i from 1 to numLaps, consider all possible segment lengths k (from 1 to maxConsecLaps), and update dp[i] as dp[i] = min(dp[i], dp[i-k] + bestTimeForK[k] + changeTime) if i != k or just bestTimeForK[k] if starting at lap 1.
  4. Return result: dp[numLaps] gives the minimum time to finish all laps.

Why it works: By precomputing the best sequences of consecutive laps for each tire, we avoid exploring every tire at every lap. The DP ensures that for every lap count we consider all possible previous segments, guaranteeing minimal total time.

Python Solution

from typing import List
import math

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
        maxConsecLaps = 0
        bestTimeForK = []

        # Step 1: precompute minimal consecutive lap times for each tire
        temp_times = []
        for f, r in tires:
            laps = []
            time = f
            total = 0
            while total + time <= f + changeTime:
                total += time
                laps.append(total)
                time *= r
            temp_times.append(laps)
            maxConsecLaps = max(maxConsecLaps, len(laps))

        # Step 2: global best times for k consecutive laps
        bestTimeForK = [math.inf] * (maxConsecLaps + 1)
        for laps in temp_times:
            for k, t in enumerate(laps, 1):
                bestTimeForK[k] = min(bestTimeForK[k], t)

        # Step 3: DP over total laps
        dp = [math.inf] * (numLaps + 1)
        dp[0] = 0
        for i in range(1, numLaps + 1):
            for k in range(1, min(i, maxConsecLaps) + 1):
                if i == k:
                    dp[i] = min(dp[i], bestTimeForK[k])
                else:
                    dp[i] = min(dp[i], dp[i-k] + changeTime + bestTimeForK[k])

        return dp[numLaps]

The implementation first computes all feasible consecutive laps for each tire until continuing becomes worse than switching. Then, it builds a global table of the best times for k laps. Finally, it uses a DP array to build the minimum total time iteratively.

Go Solution

import (
    "math"
)

func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int {
    maxConsecLaps := 0
    tempTimes := [][]int{}

    // Step 1: precompute consecutive lap times per tire
    for _, tire := range tires {
        f, r := tire[0], tire[1]
        laps := []int{}
        time := f
        total := 0
        for total + time <= f + changeTime {
            total += time
            laps = append(laps, total)
            time *= r
            if time > 1e12 { // prevent overflow
                break
            }
        }
        tempTimes = append(tempTimes, laps)
        if len(laps) > maxConsecLaps {
            maxConsecLaps = len(laps)
        }
    }

    // Step 2: global best times for k consecutive laps
    bestTimeForK := make([]int, maxConsecLaps + 1)
    for i := 1; i <= maxConsecLaps; i++ {
        bestTimeForK[i] = math.MaxInt64
    }

    for _, laps := range tempTimes {
        for k, t := range laps {
            if bestTimeForK[k+1] > t {
                bestTimeForK[k+1] = t
            }
        }
    }

    // Step 3: DP over laps
    dp := make([]int, numLaps + 1)
    for i := 1; i <= numLaps; i++ {
        dp[i] = math.MaxInt64
        for k := 1; k <= i && k <= maxConsecLaps; k++ {
            if i == k {
                if dp[i] > bestTimeForK[k] {
                    dp[i] = bestTimeForK[k]
                }
            } else {
                if dp[i] > dp[i-k] + changeTime + bestTimeForK[k] {
                    dp[i] = dp[i-k] + changeTime + bestTimeForK[k]
                }
            }
        }
    }

    return dp[numLaps]
}

In Go, care is taken to handle potential integer overflow when multiplying large numbers. The logic mirrors the Python version closely, with slices replacing lists.

Worked Examples

Example 1: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4

Precompute consecutive lap times:

  • Tire 0: [2, 6, 18] → stop at 18 > 2 + 5 = 7, so [2, 6]
  • Tire 1: [3, 12, 48] → stop at 12 > 3 + 5 = 8, so [3]

Global best times: [0, 2, 6]

DP:

  • dp[1] =