Skip to content
Hello Python

Car Fleet

Interview ProblemAdvancedMediumMonotonic StackArrayStack

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.carFleet(target, position, speed). Cars move toward target without passing; a faster car catching a slower one forms a fleet. Return the number of fleets arriving at target.

Starter code

class Solution:
    def carFleet(self, target, position, speed):
        pass
Test cases

three-fleets

{
  "args": [
    12,
    [
      10,
      8,
      0,
      5,
      3
    ],
    [
      2,
      4,
      1,
      1,
      3
    ]
  ]
}

Expected: 3

Wizard outline
  1. Step 1: Initialize Solution.carFleet

    Replace the empty starter with the first real state owned by Solution.carFleet. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

  2. Step 2: Assemble the primary transition

    Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

  3. Step 3: Pass the One Car case

    Complete the readable core algorithm for one representative Interview case. Sort cars from closest to target and compare arrival times with the fleet immediately ahead.

  4. Step 4: Harden the Same Arrival boundary

    Repair the reviewed boundary and pass the complete submission contract. Processing front to back, a car with no later arrival than the fleet ahead catches it by target and merges. A strictly later arrival cannot catch that fleet and starts a new one. Thus each counted time corresponds to exactly one fleet.

Footguns and prerequisites
  • Equal arrival times merge into one fleet, so only a strictly larger time starts a new fleet.
  • arrays strings two pointers sliding window
Reviewed references
Practice prerequisites
  • Maintain a Monotonic Stack(opens in a new tab)

    Maintain a Monotonic Stack isolates stack indices increase from bottom to top and their values are strictly increasing after invalid candidates are removed. That focused state discipline is required when implementing car fleet as a complete Interview Problem.

Recommended approach and implementation

Sort position-speed pairs by descending position. Compute time to target; count a new fleet only when this time is strictly greater than the slowest arrival time already ahead.

Why it works: Processing front to back, a car with no later arrival than the fleet ahead catches it by target and merges. A strictly later arrival cannot catch that fleet and starts a new one. Thus each counted time corresponds to exactly one fleet.

class Solution:
    def carFleet(self, target, position, speed):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        latest_time = -1
        fleets = 0
        for start, velocity in sorted(zip(position, speed), reverse=True):
            arrival = (target - start) / velocity
            if arrival > latest_time:
                fleets += 1
                latest_time = arrival
        return fleets