Minimum time to finish the race

Array Dynamic Programming

43.3% acceptance

Feb 25, 2026

602

You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri]. The ith tire finishes its xth lap in fi * ri^(x-1) seconds. You are given changeTime and numLaps. Return the minimum time to finish the race.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_finish_time(tires: Vec<Vec<i32>>, change_time: i32, num_laps: i32) -> i32 {
    let n = num_laps as usize;
    let ct = change_time as i64;

    // best[j] = min time for j consecutive laps without changing tires
    let max_j = 18usize; // r>=2: r^17 > 1e5 which exceeds any useful threshold
    let mut best = vec![i64::MAX / 2; max_j + 1];

    for tire in &tires {
      let (f, r) = (tire[0] as i64, tire[1] as i64);
      let mut total = 0i64;
      let mut lap_time = f;
      for j in 1..=max_j {
        total += lap_time;
        if total < best[j] {
          best[j] = total;
        }
        if lap_time > f + ct {
          break;
        }
        lap_time *= r;
      }
    }

    // dp[i] = min time to complete i laps
    // Use dp[0] = -changeTime so formula dp[i-j] + ct + best[j] works uniformly
    let mut dp = vec![i64::MAX / 2; n + 1];
    dp[0] = -ct;
    for i in 1..=n {
      for j in 1..=i.min(max_j) {
        if best[j] < i64::MAX / 2 && dp[i - j] < i64::MAX / 2 {
          dp[i] = dp[i].min(dp[i - j] + ct + best[j]);
        }
      }
    }
    dp[n] as i32
  }
}