Car Fleet

Cars on a one-lane road cannot pass each other. A faster car behind a slower one just bunches up and matches its speed. The question asks how many separate groups reach the finish line. The trick is to stop thinking about speed and start thinking about arrival time. Once you do that, a stack solves it.

🎯 The Problem

You return how many separate groups of cars reach the target.

• The target is where the road ends.
• You get a list of car positions and a matching list of speeds.
• The road has one lane, so a car can never pass the car ahead.
• A faster car that catches the slower car in front slows down and they move together.
• A group of cars moving together is a fleet.

Let us use target 12, positions [10, 8, 0, 5, 3], and speeds [2, 4, 1, 1, 3]. For each car work out the time to reach the target. That is distance left divided by speed. The car at 10 needs 1. The car at 8 needs 1. The car at 0 needs 12. The car at 5 needs 7. The car at 3 needs 3.

Input:  target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3

Explanation: the cars form 3 fleets that reach the target.

Here is the road as a picture. The target is on the right, and cars sit at their positions.

🐢 Approach 1: Simulate Every Moment (Brute Force)

Move time forward in tiny steps and watch the cars bunch up.

The idea:

• Step time forward a little at a time.
• Update every car’s position at each step.

How it works:

• When a car catches the one ahead, glue them together.
• Keep going until all cars reach the target.
• Count the groups at the end.

Why it is weak:

• You do not know how small the time steps must be.
• Tiny steps mean huge numbers of updates.
• Big steps might miss the exact moment two cars meet.
• It is hard to get right and has no clean time bound.

Here is the direct arrival-time simulation:

def car_fleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    fleets = 0
    slowest_time = 0

    for pos, spd in cars:
        time = (target - pos) / spd
        if time > slowest_time:
            fleets += 1
            slowest_time = time
    return fleets

⚡ Approach 2: Sort and Use a Stack of Times (Best)

The idea in one line: forget moving the cars, just compare when each one would reach the target.

The idea:

• For each car compute its arrival time, which is (target - position) / speed.
• Sort cars by position, closest to the target first.
• A car can only be blocked by a car ahead, so the fleet ahead is already decided.

How it works:

• Keep a stack of fleet arrival times. The top is the fleet just ahead.
• If a car’s time is bigger than the fleet ahead, it arrives later, so it never catches up. Push it as a new fleet.
• If its time is smaller or equal, it catches up and joins. Do not push.

Why it is fast:

• One sort, then a single walk through the cars.
• The number of items on the stack at the end is the number of fleets.

Here is the dry run for our example. Cars are sorted by position, closest first. Watch the stack of fleet times grow.

Steps to Solve

1. Pair each car with its position and speed.
2. Sort the cars by position, from closest to the target down to farthest.
3. Make an empty stack of fleet arrival times.
4. For each car compute its arrival time, which is target minus position divided by speed.
5. If that time is bigger than the time on top of the stack, push it as a new fleet. Otherwise it joins the fleet ahead.
6. The number of items on the stack is the answer.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int position;
    double time;  // arrival time at the target
} Car;

// sort by position descending (closest to target first)
int compare(const void *a, const void *b) {
    return ((Car *)b)->position - ((Car *)a)->position;
}

int carFleet(int target, int position[], int speed[], int n) {
    Car cars[1000];
    for (int i = 0; i < n; i++) {
        cars[i].position = position[i];
        cars[i].time = (double)(target - position[i]) / speed[i];
    }
    qsort(cars, n, sizeof(Car), compare);
    int fleets = 0;
    double slowest = -1.0;  // time of the fleet ahead
    for (int i = 0; i < n; i++) {
        if (cars[i].time > slowest) {  // arrives later, new fleet
            fleets++;
            slowest = cars[i].time;
        }
    }
    return fleets;
}

int main(void) {
    int position[] = {10, 8, 0, 5, 3};
    int speed[] = {2, 4, 1, 1, 3};
    int target = 12;
    printf("%d\n", carFleet(target, position, speed, 5));
    return 0;
}

3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int n = position.size();
    vector<pair<int, double>> cars;  // position, arrival time
    for (int i = 0; i < n; i++) {
        double time = (double)(target - position[i]) / speed[i];
        cars.push_back({position[i], time});
    }
    // sort by position descending (closest to target first)
    sort(cars.begin(), cars.end(), [](auto& a, auto& b) {
        return a.first > b.first;
    });
    int fleets = 0;
    double slowest = -1.0;  // time of the fleet ahead
    for (auto& car : cars) {
        if (car.second > slowest) {  // arrives later, new fleet
            fleets++;
            slowest = car.second;
        }
    }
    return fleets;
}

int main() {
    vector<int> position = {10, 8, 0, 5, 3};
    vector<int> speed = {2, 4, 1, 1, 3};
    int target = 12;
    cout << carFleet(target, position, speed) << endl;
    return 0;
}

3

import java.util.Arrays;

public class CarFleet {
    public static int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        // sort indices by position descending (closest to target first)
        Arrays.sort(idx, (a, b) -> position[b] - position[a]);
        int fleets = 0;
        double slowest = -1.0;  // time of the fleet ahead
        for (int i = 0; i < n; i++) {
            int j = idx[i];
            double time = (double)(target - position[j]) / speed[j];
            if (time > slowest) {   // arrives later, new fleet
                fleets++;
                slowest = time;
            }
        }
        return fleets;
    }

    public static void main(String[] args) {
        int[] position = {10, 8, 0, 5, 3};
        int[] speed = {2, 4, 1, 1, 3};
        int target = 12;
        System.out.println(carFleet(target, position, speed));
    }
}

3

def car_fleet(target, position, speed):
    # pair each car and sort by position, closest to target first
    cars = sorted(zip(position, speed), reverse=True)
    stack = []  # arrival times of fleets
    for pos, spd in cars:
        time = (target - pos) / spd      # how long this car takes
        # if it would catch the fleet ahead, it joins (do not push)
        if not stack or time > stack[-1]:
            stack.append(time)           # a new fleet
    return len(stack)


position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]
target = 12
print(car_fleet(target, position, speed))

3

function carFleet(target, position, speed) {
  // pair each car and sort by position, closest to target first
  const cars = position
    .map((pos, i) => [pos, speed[i]])
    .sort((a, b) => b[0] - a[0]);
  const stack = []; // arrival times of fleets
  for (const [pos, spd] of cars) {
    const time = (target - pos) / spd; // how long this car takes
    if (stack.length === 0 || time > stack[stack.length - 1]) {
      stack.push(time); // a new fleet
    }
  }
  return stack.length;
}

const position = [10, 8, 0, 5, 3];
const speed = [2, 4, 1, 1, 3];
const target = 12;
console.log(carFleet(target, position, speed));

3

Let us read the Python version line by line and see why each line is written this way.

The line cars = sorted(zip(position, speed), reverse=True) does two jobs. The zip glues each position to its speed, so they stay together. Then sorted(..., reverse=True) sorts the pairs from the largest position down to the smallest. Largest position means closest to the target. We process front cars first because a car can only be blocked by a car ahead of it. So cars becomes [(10,2), (8,4), (5,1), (3,3), (0,1)].

The line stack = [] holds the arrival times of the fleets we have found. The loop for pos, spd in cars reads each car from front to back. The line time = (target - pos) / spd is the arrival time. It is the distance left divided by the speed.

The check if not stack or time > stack[-1] is the heart of it. stack[-1] is the time of the fleet just ahead. If the stack is empty, this is the first car, so it must be a new fleet. If this car’s time is bigger than the fleet ahead, it arrives later, so it can never catch up. That makes it a new fleet, and stack.append(time) records it. If its time is smaller or equal, it would catch the fleet ahead and join it. In that case we do nothing, so it is not counted again. At the end return len(stack) gives the number of fleets.

⏱️ Time and Space Complexity

The sort is the heavy step, so the time is O(n log n), where n is the number of cars. After sorting we just walk through the cars once, which is O(n). The stack and the sorted list each hold up to n items, so the space is O(n). The simulation approach has no clean bound and is far worse in practice.

🧩 Key Takeaways

• ✅ A fleet is a group of cars that reach the target together because they cannot pass.
• ✅ Stop thinking about speed. Compute each car’s arrival time instead.
• ✅ Sort cars by position from closest to the target down to farthest.
• ✅ A car that arrives later than the fleet ahead becomes a new fleet. Otherwise it joins.
• ✅ The number of items on the stack at the end is the number of fleets.

🚀 What’s Next?

• Daily Temperatures
• Generate Parentheses