Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Each tire type is described by [f, r]. A fresh tire completes its first lap in f seconds, but keeping it for consecutive laps makes it geometrically slower: its next lap times are f, f * r, f * r^2, and so on. There is an unlimited supply of every tire type. Between laps, the driver may spend changeTime seconds to put on any fresh tire.

The task is to finish exactly numLaps laps as quickly as possible. The important choice is not really which tire is active after every individual lap. It is how to split the race into uninterrupted stints, where each stint uses one fresh tire for several consecutive laps.

Deriving the optimal solution

A dynamic program that tracks every tire and its current wear does far too much work. The tire’s next-lap time grows exponentially, which gives a useful cutoff.

Let fastest_first_lap be the smallest first-lap time among all tire types. Before any lap, changing to a fresh copy of that tire would cost

$$ \text{changeTime} + \text{fastest_first_lap}. $$

If the current worn tire’s next lap would take more than that long, continuing cannot be better. A change is faster for the immediate lap and leaves a fresh tire for the future. Therefore, only a small number of consecutive laps can ever belong to an optimal stint.

This observation leads to two compact phases.

First, precompute best_stint_time[k]: the minimum time needed to run exactly k consecutive laps without a tire change. For each tire type, add its geometric lap times one at a time and update the best value for every useful k. Stop examining that tire as soon as its next lap exceeds the replacement cutoff.

Second, treat the full race as a sequence of those precomputed stints. Let minimum_total[laps] be the minimum time to finish exactly laps laps. If the last stint has length k, everything before it costs minimum_total[laps - k], the pit stop costs changeTime, and the stint costs best_stint_time[k]. Thus,

$$ \text{minimum_total}[i]

\min_k\left( \text{minimum_total}[i-k]

  • \text{changeTime}
  • \text{best_stint_time}[k] \right). $$

The race does not require a tire change before its first stint, so initialize minimum_total[0] to -changeTime. That one bookkeeping trick cancels the extra pit-stop charge added by the recurrence.

For example, with tires = [[2, 3], [3, 4]] and changeTime = 5, the replacement cutoff is 7. The first tire can run one lap in 2 seconds or two consecutive laps in 2 + 6 = 8 seconds; its third lap would already take 18 seconds. For four laps, the dynamic program chooses two two-lap stints: 8 + 5 + 8 = 21 seconds.

The precomputation is sufficient because every possible race plan can be divided at its tire changes into uninterrupted stints. Replacing each stint by the cheapest precomputed stint of the same length never makes the plan worse. The recurrence tries every useful length for the final stint, so it considers the optimal plan’s final split and builds the global optimum from optimal smaller races.

If there are T tire types, N laps, and at most K useful consecutive laps on one tire, the running time is $O(TK + NK)$ and the space usage is $O(N + K)$. Because every degradation factor is at least 2, K grows only logarithmically with the replacement cutoff and is very small under the problem constraints.

Python solution

from math import inf


class Solution:
    """Compute the fastest race using short tire stints and dynamic programming."""

    def minimumFinishTime(
        self,
        tires: list[list[int]],
        changeTime: int,
        numLaps: int,
    ) -> int:
        """Return the minimum number of seconds needed to finish the race."""
        self._validate_inputs(tires, changeTime, numLaps)

        best_stint_time, maximum_stint_length = self._precompute_stint_times(
            tires,
            changeTime,
            numLaps,
        )

        # Every transition below adds a pit-stop cost. Starting at -changeTime
        # cancels that cost for the race's first stint.
        minimum_total = [inf] * (numLaps + 1)
        minimum_total[0] = -changeTime

        for completed_laps in range(1, numLaps + 1):
            longest_final_stint = min(completed_laps, maximum_stint_length)

            for stint_length in range(1, longest_final_stint + 1):
                candidate = (
                    minimum_total[completed_laps - stint_length]
                    + changeTime
                    + best_stint_time[stint_length]
                )
                if candidate < minimum_total[completed_laps]:
                    minimum_total[completed_laps] = candidate

        return int(minimum_total[numLaps])

    @staticmethod
    def _precompute_stint_times(
        tires: list[list[int]],
        change_time: int,
        num_laps: int,
    ) -> tuple[list[float], int]:
        """Find the cheapest uninterrupted stint for every useful length."""
        fastest_first_lap = min(first_lap for first_lap, _ in tires)
        replacement_cutoff = change_time + fastest_first_lap

        best_stint_time = [inf] * (num_laps + 1)
        maximum_stint_length = 0

        for first_lap, degradation_factor in tires:
            elapsed_time = 0
            current_lap_time = first_lap
            stint_length = 1

            # Above the cutoff, changing to the fastest fresh tire is faster.
            # Keeping equality also supports a zero-cost-change defensive case.
            while (
                stint_length <= num_laps
                and current_lap_time <= replacement_cutoff
            ):
                elapsed_time += current_lap_time
                if elapsed_time < best_stint_time[stint_length]:
                    best_stint_time[stint_length] = elapsed_time

                maximum_stint_length = max(
                    maximum_stint_length,
                    stint_length,
                )
                current_lap_time *= degradation_factor
                stint_length += 1

        return best_stint_time, maximum_stint_length

    @staticmethod
    def _validate_inputs(
        tires: list[list[int]],
        change_time: int,
        num_laps: int,
    ) -> None:
        """Reject malformed inputs when this method is reused outside LeetCode."""
        if not tires:
            raise ValueError("tires must contain at least one tire type")
        if change_time < 0:
            raise ValueError("changeTime must be nonnegative")
        if num_laps <= 0:
            raise ValueError("numLaps must be positive")

        for tire in tires:
            if len(tire) != 2:
                raise ValueError("each tire must contain [first_lap, factor]")

            first_lap, degradation_factor = tire
            if first_lap <= 0 or degradation_factor <= 1:
                raise ValueError(
                    "tire first-lap times must be positive and factors "
                    "must exceed one"
                )

Interview follow-ups

Why is it safe to stop considering a tire at the replacement cutoff?

Suppose a worn tire’s next lap takes more than changeTime + fastest_first_lap. Changing to the fastest fresh tire is then strictly faster for that lap. After the lap, the changed plan also has a less-worn tire, so it cannot be worse on any later lap.

If the two choices tie on the immediate lap, the reset is still at least as good for the future. The implementation harmlessly retains that equality case, which also makes the method work when a reused caller supplies a zero tire-change cost. This dominance argument proves that no laps beyond the cutoff are needed and explains why the exponential tire behavior does not make the algorithm expensive.

How would the solution return the actual tire and pit-stop plan?

During precomputation, store the tire index that achieves each best_stint_time[k]. During the race dynamic program, store the chosen final stint_length whenever a candidate improves minimum_total[laps]. Starting at numLaps, repeatedly subtract the recorded length to reconstruct all stints in reverse order, then pair each length with its recorded tire index.

The optimality proof does not change: the added arrays only remember which already-optimal transition produced each state. Reconstruction takes $O(N)$ time in the worst case. The asymptotic precomputation and dynamic-programming costs remain $O(TK + NK)$ time and $O(N + K)$ space.

Can the dynamic program use less memory?

Yes. A state for i laps only reads states from i - 1 through i - K, so the full minimum_total array can be replaced by a circular buffer of size K + 1. Each new value overwrites a state that is too old to be used again.

This reduces the race-DP memory from $O(N)$ to $O(K)$ while preserving $O(NK)$ time. The full array is usually preferable in an interview because it is simpler and allows plan reconstruction; the circular buffer is most useful when only the minimum time is required and N is large.

What changes if each tire type has only a limited inventory?

The current reduction relies on unlimited fresh copies, which makes the best stint of a given length reusable any number of times. With limited inventories, choosing a tire now changes which stints are available later. A one-dimensional state indexed only by completed laps no longer contains enough information.

For small inventories, the dynamic-programming state can include how many copies of each tire type have been consumed, often encoded as a mixed-radix integer or tuple. A transition chooses a remaining tire and a stint length. This is correct because the state now captures every resource that affects future choices, but its size grows as the product of the inventory limits and quickly becomes exponential in the number of tire types.

What if the tire-change cost depends on the old and new tire types?

Then stint length alone is not enough because the cost of the next transition depends on the previous tire. Precompute each tire type’s uninterrupted stint costs separately, and define a state such as dp[laps][last_tire], meaning the cheapest way to finish laps laps with a stint on last_tire at the end.

A transition considers the preceding tire, the new tire, and the new stint length, adding the appropriate pair-specific change cost. The state restores the information needed for correct future costs, but a direct implementation adds a quadratic factor in the number of tire types. If the transition-cost matrix has special structure, such as depending only on the new tire or splitting into an old-tire term plus a new-tire term, that factor may be optimized away.

How could the approach handle an enormous number of laps?

The recurrence has a fixed maximum lookback of K, so it can be viewed as a shortest-path transition over the last K dynamic-programming positions. For moderately large N, the existing $O(NK)$ algorithm remains the clearest choice and can use the circular-buffer optimization.

If N is so large that even linear time is unacceptable, encode one recurrence step as a min-plus transition matrix and exponentiate that matrix. Min-plus multiplication combines path costs using minimum and addition, exactly matching the recurrence. This can reduce the dependence on N to logarithmic, at the cost of roughly $O(K^3 \log N)$ time and more complex code. It is useful only when K is small and N is extremely large.