Car fleet ii

Array Math Stack Heap (Priority Queue) Monotonic Stack

57.8% acceptance

Feb 25, 2026

963

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi]. Once a car collides with another car, they unite and form a single car fleet with the speed of the slower car. Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1.0 if no collision.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_collision_times(cars: Vec<Vec<i32>>) -> Vec<f64> {
    let n = cars.len();
    let mut ans = vec![-1.0f64; n];
    // Stack: indices of cars, monotone by decreasing speed
    let mut stack: Vec<usize> = Vec::new();

    for i in (0..n).rev() {
      let (pi, si) = (cars[i][0] as f64, cars[i][1] as f64);
      // pop cars from stack that car i cannot catch
      loop {
        if stack.is_empty() { break; }
        let j = *stack.last().unwrap();
        let (pj, sj) = (cars[j][0] as f64, cars[j][1] as f64);
        if si <= sj {
          // car i is slower than j, can't catch j
          stack.pop();
          continue;
        }
        // time to catch j: (pj - pi) / (si - sj)
        let t = (pj - pi) / (si - sj);
        // If this catch time >= j's own catch time (j will already be part of fleet)
        // then j effectively doesn't exist for i
        if ans[j] > 0.0 && t >= ans[j] {
          stack.pop();
          continue;
        }
        ans[i] = t;
        break;
      }
      stack.push(i);
    }
    ans
  }
}