Skip to main content
CodePeetCodePeet
CodePeet 250

Car Fleet

MEDIUMProblemSolveExternal Links

Description

There are n cars positioned at various miles along a one-way road, all heading toward a common destination located at mile target.

You are given two integer arrays position and speed, both of length n. Here, position[i] represents the starting mile of the i-th car, and speed[i] represents how many miles per hour that car travels.

A critical rule governs this road: a car can never overtake another car in front of it. If a faster car catches up to a slower car ahead, the faster car must slow down and travel alongside the slower one at the slower car's speed. Together, they form what is called a car fleet.

A car fleet can be a single car traveling alone, or a group of cars that have merged together. The fleet's speed equals the speed of its slowest member. Importantly, if a car catches up to a fleet right at mile target, that car still joins the fleet.

Your task is to determine how many distinct car fleets will arrive at the destination.

Examples

Example 1

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

Output: 3

Explanation:

  • The car at position 10 (speed 2) needs (12 - 10) / 2 = 1 hour to reach the target. The car at position 8 (speed 4) needs (12 - 8) / 4 = 1 hour. Since the car at 8 catches up to the car at 10 exactly at the target, they form one fleet.
  • The car at position 5 (speed 1) needs (12 - 5) / 1 = 7 hours. The car at position 3 (speed 3) needs (12 - 3) / 3 = 3 hours. Since car at 3 is faster, it catches up to car at 5 at mile 6 and they merge into a fleet traveling at speed 1. This fleet takes 7 hours total.
  • The car at position 0 (speed 1) needs (12 - 0) / 1 = 12 hours. It never catches up to anyone ahead, so it travels alone.

Three separate fleets arrive at the destination.

Example 2

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation: There is only one car on the road, so there is exactly one fleet.

Example 3

Input: target = 100, position = [0, 2, 4], speed = [4, 2, 1]

Output: 1

Explanation:

  • The car at position 0 (speed 4) catches the car at position 2 (speed 2) at mile 4. They merge into a fleet traveling at speed 2.
  • That fleet then catches the car at position 4 (speed 1) at mile 6. All three cars merge into a single fleet traveling at speed 1.
  • Only one fleet arrives at the destination.

Constraints

  • n == position.length == speed.length
  • 1 ≤ n ≤ 10^5
  • 0 < target ≤ 10^6
  • 0 ≤ position[i] < target
  • All values of position are unique
  • 0 < speed[i] ≤ 10^6

Editorial

Brute Force

Intuition

The most direct way to think about this problem is to simulate the movement of cars step by step. Imagine you are watching the road from above, ticking the clock forward second by second (or in very small increments). At each tick, every car moves forward by its speed. If a car reaches or passes the car ahead of it, they merge into a fleet, and the merged group now moves at the slower car's speed.

To implement this naively, we can first sort cars by their position so we know who is ahead of whom. Then for each pair of adjacent cars (when sorted by position), we check: will the car behind ever catch up to the car in front before the target?

The key observation is that a car behind catches the car in front only if the behind car's time to reach the target is less than or equal to the front car's time. If the behind car would arrive faster (lower time), it must be going fast enough to catch up, and they merge. Otherwise, they stay as separate fleets.

So the brute force idea is: sort cars by position, compute each car's arrival time at the target, then iterate through pairs to count how many distinct fleets form. For each car, we check against the car directly ahead and decide whether they merge.

Step-by-Step Explanation

Let's trace through Example 1: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

Step 1: Sort cars by position in ascending order.

  • Sorted: [(0,1), (3,3), (5,1), (8,4), (10,2)] → positions [0, 3, 5, 8, 10], speeds [1, 3, 1, 4, 2]

Step 2: Compute arrival time for each car.

  • Car at 0: (12 - 0) / 1 = 12.0 hours
  • Car at 3: (12 - 3) / 3 = 3.0 hours
  • Car at 5: (12 - 5) / 1 = 7.0 hours
  • Car at 8: (12 - 8) / 4 = 1.0 hours
  • Car at 10: (12 - 10) / 2 = 1.0 hours
  • Times array: [12.0, 3.0, 7.0, 1.0, 1.0]

Step 3: Starting from the car closest to target (rightmost), group cars into fleets.

  • Start with car at position 10, time = 1.0. This is our first fleet. Fleet count = 1.

Step 4: Check car at position 8, time = 1.0.

  • Is 1.0 ≤ 1.0 (the fleet ahead's time)? Yes. Car at 8 catches up to the fleet at 10. They merge. The fleet's time remains 1.0.

Step 5: Check car at position 5, time = 7.0.

  • Is 7.0 ≤ 1.0? No. Car at 5 is much slower and cannot catch up. It forms a new fleet. Fleet count = 2. Current fleet time = 7.0.

Step 6: Check car at position 3, time = 3.0.

  • Is 3.0 ≤ 7.0? Yes. Car at 3 catches up to the fleet anchored by car at 5. They merge. Fleet time stays 7.0.

Step 7: Check car at position 0, time = 12.0.

  • Is 12.0 ≤ 7.0? No. Car at 0 is too slow. It forms a new fleet. Fleet count = 3.

Result: 3 fleets.

Brute Force — Sorting Cars and Comparing Arrival Times — Watch how we sort cars by position, compute arrival times, and scan from the car closest to the target to count separate fleets.

Algorithm

  1. Pair each car's position with its speed and sort by position in ascending order.
  2. Compute the arrival time for each car: time[i] = (target - position[i]) / speed[i].
  3. Starting from the car closest to the target (rightmost), initialize fleet count = 1 and set the current fleet's time to the rightmost car's arrival time.
  4. For each subsequent car moving leftward:
    • If this car's arrival time is greater than the current fleet's time, it cannot catch up. Increment fleet count and update the current fleet's time.
    • Otherwise, the car merges into the current fleet (do nothing).
  5. Return the fleet count.

Code

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

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        if (n == 0) return 0;
        
        // Pair positions with speeds and sort by position
        vector<pair<int,int>> cars(n);
        for (int i = 0; i < n; i++) {
            cars[i] = {position[i], speed[i]};
        }
        sort(cars.begin(), cars.end());
        
        // Compute arrival times
        vector<double> times(n);
        for (int i = 0; i < n; i++) {
            times[i] = (double)(target - cars[i].first) / cars[i].second;
        }
        
        // Scan from closest to target (rightmost) to farthest
        int fleets = 1;
        double currentFleetTime = times[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (times[i] > currentFleetTime) {
                fleets++;
                currentFleetTime = times[i];
            }
        }
        
        return fleets;
    }
};
class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        n = len(position)
        if n == 0:
            return 0
        
        # Pair positions with speeds and sort by position
        cars = sorted(zip(position, speed))
        
        # Compute arrival times
        times = [(target - pos) / spd for pos, spd in cars]
        
        # Scan from closest to target to farthest
        fleets = 1
        current_fleet_time = times[-1]
        for i in range(n - 2, -1, -1):
            if times[i] > current_fleet_time:
                fleets += 1
                current_fleet_time = times[i]
        
        return fleets
import java.util.Arrays;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        if (n == 0) return 0;
        
        // Create index array and sort by position
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> position[a] - position[b]);
        
        // Compute arrival times
        double[] times = new double[n];
        for (int i = 0; i < n; i++) {
            times[i] = (double)(target - position[indices[i]]) / speed[indices[i]];
        }
        
        // Scan from closest to target
        int fleets = 1;
        double currentFleetTime = times[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (times[i] > currentFleetTime) {
                fleets++;
                currentFleetTime = times[i];
            }
        }
        
        return fleets;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the cars by position takes O(n log n). Computing arrival times takes O(n). The single scan to count fleets takes O(n). The dominant term is the sorting step, giving O(n log n) overall.

Space Complexity: O(n)

We store the paired cars array and the times array, each of size n. The sorting step also uses O(n) auxiliary space (depending on the sort implementation). Total space is O(n).

Why This Approach Is Not Efficient

Actually, the brute force approach described above already runs in O(n log n) time, which is quite efficient. The sorting step dominates, and the linear scan is optimal. For this particular problem, there is no way to avoid sorting (or an equivalent ordering step) because fleet formation depends on the spatial ordering of cars.

However, the approach can be refined in terms of clarity and elegance. The current approach uses a simple variable to track the 'blocking time', but a more structured and instructive approach uses a stack data structure. The stack-based approach makes the fleet merging logic more explicit and is more generalizable to related problems like Car Fleet II. While it has the same O(n log n) time complexity, it is worth understanding as an alternative implementation.

Optimal Approach - Stack-Based Fleet Counting

Intuition

Let's think about this problem from the perspective of the destination, looking backward. The car closest to the target is the most important one to consider first, because it acts as a potential "blocker" for all cars behind it.

Imagine you are standing at the target mile, looking back down the road. The nearest car will arrive at some specific time. Now look at the next nearest car. If that car would arrive sooner than the first car (if traveling unimpeded), it means the second car is fast enough to catch up — so it joins the first car's fleet. But if the second car would arrive later, it is too slow to ever catch the first car, and it forms its own independent fleet.

This naturally suggests a stack: we process cars from closest to farthest from the target. For each car, we compute its theoretical arrival time. We push this time onto the stack only if it represents a new fleet (i.e., the arrival time is strictly greater than the current stack top). If the arrival time is less than or equal to the top, the car merges into the existing fleet and we do not push.

At the end, the number of elements on the stack equals the number of distinct fleets.

The key insight is: a car's arrival time at the target determines everything. If you would arrive later than the car ahead of you, you are in your own fleet. If you would arrive earlier or at the same time, you get absorbed into the fleet ahead.

Step-by-Step Explanation

Let's trace through Example 1: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]

Step 1: Sort cars by position descending (closest to target first).

  • Sorted: [(10, 2), (8, 4), (5, 1), (3, 3), (0, 1)]

Step 2: Compute arrival time for car at position 10: (12 - 10) / 2 = 1.0

  • Stack is empty. Push 1.0. Stack = [1.0]

Step 3: Compute arrival time for car at position 8: (12 - 8) / 4 = 1.0

  • Compare 1.0 with stack top 1.0. Is 1.0 > 1.0? No. Car merges into existing fleet. Do not push.
  • Stack = [1.0]

Step 4: Compute arrival time for car at position 5: (12 - 5) / 1 = 7.0

  • Compare 7.0 with stack top 1.0. Is 7.0 > 1.0? Yes. Car is slower — forms a new fleet. Push 7.0.
  • Stack = [1.0, 7.0]

Step 5: Compute arrival time for car at position 3: (12 - 3) / 3 = 3.0

  • Compare 3.0 with stack top 7.0. Is 3.0 > 7.0? No. Car merges into existing fleet. Do not push.
  • Stack = [1.0, 7.0]

Step 6: Compute arrival time for car at position 0: (12 - 0) / 1 = 12.0

  • Compare 12.0 with stack top 7.0. Is 12.0 > 7.0? Yes. Car is the slowest — forms a new fleet. Push 12.0.
  • Stack = [1.0, 7.0, 12.0]

Step 7: All cars processed. Stack size = 3.

Result: 3 fleets.

Stack-Based Fleet Counting — Processing Cars from Target Backward — Watch how we process cars from closest to the target to farthest, pushing arrival times onto a stack only when a new fleet forms. Cars that catch up are absorbed and not pushed.

Algorithm

  1. Pair each car's position with its speed.
  2. Sort the pairs by position in descending order (closest to target first).
  3. Initialize an empty stack.
  4. For each car in the sorted order:
    a. Compute arrival time: (target - position) / speed.
    b. If the stack is empty OR this arrival time is strictly greater than the stack top:
    • Push the arrival time onto the stack (new fleet).
      c. Otherwise, this car merges into the existing fleet (do nothing).
  5. Return the size of the stack — this equals the number of fleets.

Code

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

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        if (n == 0) return 0;
        
        // Pair and sort by position descending
        vector<pair<int,int>> cars(n);
        for (int i = 0; i < n; i++) {
            cars[i] = {position[i], speed[i]};
        }
        sort(cars.begin(), cars.end(), [](auto& a, auto& b) {
            return a.first > b.first;
        });
        
        stack<double> stk;
        for (auto& [pos, spd] : cars) {
            double time = (double)(target - pos) / spd;
            if (stk.empty() || time > stk.top()) {
                stk.push(time);
            }
        }
        
        return stk.size();
    }
};
class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        n = len(position)
        if n == 0:
            return 0
        
        # Pair and sort by position descending (closest to target first)
        cars = sorted(zip(position, speed), reverse=True)
        
        stack = []
        for pos, spd in cars:
            arrival_time = (target - pos) / spd
            if not stack or arrival_time > stack[-1]:
                stack.append(arrival_time)
        
        return len(stack)
import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        if (n == 0) return 0;
        
        // Create index array sorted by position descending
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> position[b] - position[a]);
        
        Stack<Double> stack = new Stack<>();
        for (int idx : indices) {
            double arrivalTime = (double)(target - position[idx]) / speed[idx];
            if (stack.isEmpty() || arrivalTime > stack.peek()) {
                stack.push(arrivalTime);
            }
        }
        
        return stack.size();
    }
}

Complexity Analysis

Time Complexity: O(n log n)

The sorting step takes O(n log n). The single pass through all n cars to build the stack takes O(n), since each car is processed exactly once with O(1) work (a comparison and possibly a push). The overall time is O(n log n), dominated by sorting.

Space Complexity: O(n)

In the worst case (all cars form separate fleets), the stack holds n elements. The sorting step also uses O(n) auxiliary space. Total space is O(n).

Note: This has the same asymptotic complexity as the brute force approach since both are fundamentally bounded by the sorting step. The stack-based approach is preferred for its clarity, its alignment with the monotonic stack pattern (useful in many related problems), and its explicit representation of fleet boundaries.