Car Fleet II

hard monotonic stack math

Problem

There are n cars on a one-lane road, all driving in the same direction. cars[i] = [position, speed] lists them rear to front with strictly increasing positions. When a car catches up to the car (or fleet) directly ahead, they collide, merge into one fleet, and continue at the slower car's speed. For each car, return the time at which it first collides with the car in front of it, or -1 if that never happens.

Scanning right to left, keep a stack of cars ahead that could still be hit: pop a car if it is at least as fast as you, or if it collides and slows down before you would ever reach it.

Inputcars = [[1,2],[2,1],[4,3],[7,2]]

Output[1.00, -1.00, 3.00, -1.00]

Car 0 closes the 1-unit gap to car 1 at relative speed 2−1 = 1 → t = 1. Car 2 closes 3 units on car 3 at relative speed 3−2 = 1 → t = 3. Cars 1 and 3 never catch anyone.

cars (position:speed, comma-separated, rear → front)

def get_collision_times(cars):
    n = len(cars)
    ans = [-1.0] * n
    stack = []                # cars ahead that could still be hit
    for i in range(n - 1, -1, -1):
        p, s = cars[i]
        while stack:
            j = stack[-1]
            pj, sj = cars[j]
            if s <= sj or (ans[j] > 0 and (pj - p) / (s - sj) >= ans[j]):
                stack.pop()   # j is uncatchable or gone too soon
            else:
                break
        if stack:
            j = stack[-1]
            ans[i] = (cars[j][0] - p) / (s - cars[j][1])
        stack.append(i)
    return ans

function getCollisionTimes(cars) {
  const n = cars.length;
  const ans = new Array(n).fill(-1);
  const stack = []; // cars ahead that could still be hit
  for (let i = n - 1; i >= 0; i--) {
    const p = cars[i][0], s = cars[i][1];
    while (stack.length) {
      const j = stack[stack.length - 1];
      const pj = cars[j][0], sj = cars[j][1];
      if (s <= sj || (ans[j] > 0 && (pj - p) / (s - sj) >= ans[j])) {
        stack.pop(); // j is uncatchable or gone too soon
      } else {
        break;
      }
    }
    if (stack.length) {
      const j = stack[stack.length - 1];
      ans[i] = (cars[j][0] - p) / (s - cars[j][1]);
    }
    stack.push(i);
  }
  return ans;
}

public double[] getCollisionTimes(int[][] cars) {
    int n = cars.length;
    double[] ans = new double[n];
    Arrays.fill(ans, -1.0);
    Deque<Integer> stack = new ArrayDeque<>(); // cars ahead
    for (int i = n - 1; i >= 0; i--) {
        int p = cars[i][0], s = cars[i][1];
        while (!stack.isEmpty()) {
            int j = stack.peek();
            int pj = cars[j][0], sj = cars[j][1];
            if (s <= sj || (ans[j] > 0 && (double) (pj - p) / (s - sj) >= ans[j])) {
                stack.pop(); // j is uncatchable or gone too soon
            } else {
                break;
            }
        }
        if (!stack.isEmpty()) {
            int j = stack.peek();
            ans[i] = (double) (cars[j][0] - p) / (s - cars[j][1]);
        }
        stack.push(i);
    }
    return ans;
}

vector<double> getCollisionTimes(vector<vector<int>>& cars) {
    int n = cars.size();
    vector<double> ans(n, -1.0);
    vector<int> stack; // cars ahead that could still be hit
    for (int i = n - 1; i >= 0; i--) {
        int p = cars[i][0], s = cars[i][1];
        while (!stack.empty()) {
            int j = stack.back();
            int pj = cars[j][0], sj = cars[j][1];
            if (s <= sj || (ans[j] > 0 && double(pj - p) / (s - sj) >= ans[j])) {
                stack.pop_back(); // j is uncatchable or gone too soon
            } else {
                break;
            }
        }
        if (!stack.empty()) {
            int j = stack.back();
            ans[i] = double(cars[j][0] - p) / (s - cars[j][1]);
        }
        stack.push_back(i);
    }
    return ans;
}

Explanation

A car can only ever hit something ahead of it, so we scan from the front-most car backwards and keep a monotonic stack of cars ahead that the current car could still run into. A car ahead becomes irrelevant for two reasons: it is at least as fast as you (you will never close the gap), or it collides and merges into a slower fleet before you would have reached it — in both cases we pop it.

The math is simple relative motion. If car i (position p, speed s) chases car j (position pj, speed sj) with s > sj, the gap pj − p shrinks at rate s − sj, so the catch time is t = (pj − p) / (s − sj). But car j stops existing at speed sj at time ans[j], when it merges into the fleet ahead. If t ≥ ans[j], car i never meets car j at that speed — the real target is some slower car deeper in the stack, so popping j is safe.

The stack stays ordered so that each car disappears strictly later than the car above it (or never, for -1). That invariant is exactly why checking only the top of the stack is enough: once the top survives both pop tests, its catch time is valid and becomes ans[i]. Then car i is pushed, becoming the nearest candidate for everything further left.

Walking the default example cars = [[1,2],[2,1],[4,3],[7,2]]: car 3 has nothing ahead → -1, push. Car 2 (speed 3) catches car 3 in (7−4)/(3−2) = 3, push. Car 1 (speed 1) pops car 2 and car 3 — both are faster — leaving an empty stack, so -1, push. Car 0 (speed 2) catches car 1 in (2−1)/(2−1) = 1. Answer: [1.00, -1, 3.00, -1].

Each car is pushed exactly once and popped at most once, so all the while-loop work across the whole scan is amortized O(n) total, and the stack plus answer array use O(n) space.

Time: O(n) Space: O(n)