title: Car Fleet II
slug: car-fleet-ii
difficulty: hard
leetcode_id: 1776
leetcode_url: https://leetcode.com/problems/car-fleet-ii/
categories:
  - arrays
  - stack
  - math
patterns:
  - slug: monotonic-stack
    is_optimal: true

function_signature: "def get_collision_times(cars: list[list[int]]) -> list[float]:"

test_cases:
  visible:
    - input: { cars: [[1, 2], [2, 1], [4, 3], [7, 2]] }
      expected: [1.0, -1.0, 3.0, -1.0]
    - input: { cars: [[3, 4], [5, 4], [6, 3], [9, 1]] }
      expected: [2.0, 1.0, 1.5, -1.0]
  hidden:
    - input: { cars: [[1, 1]] }
      expected: [-1.0]
    - input: { cars: [[1, 2], [2, 1]] }
      expected: [1.0, -1.0]
    - input: { cars: [[1, 1], [2, 2], [3, 3]] }
      expected: [-1.0, -1.0, -1.0]
    - input: { cars: [[1, 3], [2, 2], [3, 1]] }
      expected: [1.0, 1.0, -1.0]
    - input: { cars: [[5, 2], [6, 2], [7, 2]] }
      expected: [-1.0, -1.0, -1.0]

description: |
  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] = [position_i, speed_i]` represents:

  - `position_i` is the distance between the i<sup>th</sup> car and the beginning of the road in meters. It is guaranteed that `position_i < position_(i+1)`.
  - `speed_i` is the initial speed of the i<sup>th</sup> car in meters per second.

  For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the **slowest** car in the fleet.

  Return an array `answer`, where `answer[i]` is the time, in seconds, at which the i<sup>th</sup> car collides with the next car, or `-1` if the car does not collide with the next car. Answers within `10^-5` of the actual answers are accepted.

constraints: |
  - `1 <= cars.length <= 10^5`
  - `1 <= position_i, speed_i <= 10^6`
  - `position_i < position_(i+1)`

examples:
  - input: "cars = [[1,2],[2,1],[4,3],[7,2]]"
    output: "[1.00000,-1.00000,3.00000,-1.00000]"
    explanation: "After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s."
  - input: "cars = [[3,4],[5,4],[6,3],[9,1]]"
    output: "[2.00000,1.00000,1.50000,-1.00000]"
    explanation: "The second car (speed 4) catches the third car (speed 3) at t=1. The third car (speed 3) catches the fourth car (speed 1) at t=1.5. The first car eventually catches up to the merged fleet."

explanation:
  intuition: |
    Imagine watching cars on a highway from a helicopter. Faster cars behind slower cars will eventually catch up and merge into a "fleet" that travels at the slower car's speed.

    The key insight is that we need to process cars **from right to left** (from the front of the road to the back). Why? Because when a car catches up to the car ahead, it adopts that car's speed. This means a car might "pass through" a collision — if the car ahead has already merged with an even slower car, the collision time calculation changes.

    Think of it like dominoes falling in reverse. The rightmost car never collides with anything (no car ahead). The second-rightmost car might collide with the rightmost. But here's the trick: if the second-rightmost car collides with the rightmost *after* the rightmost has already merged with something else, we need to recalculate based on the merged fleet's speed.

    This naturally leads to a **monotonic stack** approach. We maintain a stack of cars that a car might potentially collide with. When processing each car, we check if it can catch the car at the top of the stack, and if that collision would happen *before* the stack car itself collides with something ahead (and changes speed).

  approach: |
    We use a **Monotonic Stack** approach, processing cars from right to left:

    **Step 1: Initialise the result array and stack**

    - `answer`: Array of size `n` initialised to `-1` (default: no collision)
    - `stack`: Stores indices of cars that could be collision targets

    &nbsp;

    **Step 2: Process cars from right to left**

    - For each car `i` from `n-1` down to `0`:
      - While the stack is not empty, check if car `i` can catch the car at stack top
      - Calculate collision time: `time = (pos[j] - pos[i]) / (speed[i] - speed[j])`
      - A collision is only valid if car `i` is faster AND the collision happens before car `j` collides with something else (or car `j` never collides)

    &nbsp;

    **Step 3: Validate collision timing**

    - If `speed[i] <= speed[j]`: Car `i` can never catch car `j` — pop from stack
    - If collision time is valid (before car `j`'s own collision or `j` has no collision): record the time
    - If collision happens *after* car `j` merges with another fleet: car `j` is no longer a valid target — pop and try the next car on the stack

    &nbsp;

    **Step 4: Push current car onto stack**

    - After finding the collision time (or determining no collision), push car `i` onto the stack
    - Cars on the stack represent potential collision targets for cars further left

    &nbsp;

    The stack maintains a monotonic property: cars that are valid collision targets. Invalid candidates get popped when they're no longer reachable.

  common_pitfalls:
    - title: Processing Left to Right
      description: |
        Processing cars from left to right seems intuitive but fails because you don't know the final speed of cars ahead.

        For example, with `cars = [[1,4],[2,3],[3,1]]`:
        - Car 0 (speed 4) will catch car 1 (speed 3)
        - But car 1 will catch car 2 (speed 1) first and slow down to speed 1
        - Now car 0 catches up to a fleet moving at speed 1, not speed 3

        Processing right to left ensures we know each car's "fate" before calculating collisions.
      wrong_approach: "Iterate left to right and calculate naive collision times"
      correct_approach: "Iterate right to left using a monotonic stack"

    - title: Ignoring Transitive Collisions
      description: |
        When car `i` would collide with car `j` *after* car `j` has already merged with car `k`, the collision time calculation `(pos[j] - pos[i]) / (speed[i] - speed[j])` is wrong.

        At that point, car `j` is traveling at car `k`'s speed. We must pop car `j` from the stack and recalculate against car `k` (or whatever car `j` merged into).

        This is why we check: `collision_time > answer[j]` (when `answer[j] != -1`). If true, the collision happens too late.
      wrong_approach: "Always use the direct collision time formula"
      correct_approach: "Pop stack elements when collision happens after their own collision"

    - title: Floating Point Precision
      description: |
        Division for collision time can lead to precision issues. The problem accepts answers within `10^-5`, so standard floating-point arithmetic is sufficient, but be careful with edge cases.

        Using `(pos[j] - pos[i]) / (speed[i] - speed[j])` is safe since `speed[i] > speed[j]` is guaranteed when we calculate (we skip cases where `speed[i] <= speed[j]`).

  key_takeaways:
    - "**Right-to-left processing**: When future states affect current calculations, process in reverse order"
    - "**Monotonic stack for collision cascades**: The stack tracks valid collision candidates, automatically handling transitive merges"
    - "**Time-based validity checks**: A collision is only valid if it happens before the target's own state change"
    - "**Pattern recognition**: This problem combines physics simulation with stack-based optimization — recognizing when brute force O(n^2) can be reduced via monotonic structures"

  time_complexity: "O(n). Each car is pushed onto and popped from the stack at most once, giving amortized O(1) per car."
  space_complexity: "O(n). The stack can hold up to `n` car indices in the worst case, plus the `answer` array of size `n`."

solutions:
  - approach_name: Monotonic Stack
    is_optimal: true
    code: |
      def get_collision_times(cars: list[list[int]]) -> list[float]:
          n = len(cars)
          # Initialise all collision times to -1 (no collision)
          answer = [-1.0] * n
          # Stack stores indices of cars that could be collision targets
          stack = []

          # Process cars from right to left (front to back of road)
          for i in range(n - 1, -1, -1):
              pos_i, speed_i = cars[i]

              # Check if current car can catch cars on the stack
              while stack:
                  j = stack[-1]  # Car at top of stack
                  pos_j, speed_j = cars[j]

                  # If car i is not faster, it can never catch car j
                  if speed_i <= speed_j:
                      stack.pop()
                      continue

                  # Calculate when car i would collide with car j
                  collision_time = (pos_j - pos_i) / (speed_i - speed_j)

                  # Check if this collision happens before car j's own collision
                  # If car j collides before car i reaches it, j is not a valid target
                  if answer[j] != -1 and collision_time > answer[j]:
                      stack.pop()
                      continue

                  # Valid collision found
                  answer[i] = collision_time
                  break

              # Push current car as potential target for cars behind it
              stack.append(i)

          return answer
    explanation: |
      **Time Complexity:** O(n) — Each car is pushed and popped from the stack at most once.

      **Space Complexity:** O(n) — Stack can hold up to n indices.

      We process cars from right to left, maintaining a stack of potential collision targets. For each car, we find the first valid target it can collide with, accounting for the fact that the target might merge with another fleet before the collision occurs.

  - approach_name: Brute Force (TLE)
    is_optimal: false
    code: |
      def get_collision_times(cars: list[list[int]]) -> list[float]:
          n = len(cars)
          answer = [-1.0] * n

          # For each car, simulate its journey
          for i in range(n - 1):
              pos_i, speed_i = cars[i]

              # Check all cars ahead
              min_time = float('inf')
              for j in range(i + 1, n):
                  pos_j, speed_j = cars[j]

                  # Can only catch if faster
                  if speed_i > speed_j:
                      time = (pos_j - pos_i) / (speed_i - speed_j)
                      # This doesn't account for car j merging first!
                      min_time = min(min_time, time)

              if min_time != float('inf'):
                  answer[i] = min_time

          return answer
    explanation: |
      **Time Complexity:** O(n^2) — Nested loops checking all pairs.

      **Space Complexity:** O(n) — Only the answer array.

      This brute force approach is incorrect for cases where transitive collisions occur. It also times out for large inputs. Included to illustrate why the monotonic stack approach is necessary — we need to track which cars are still "active" targets.
