Car Fleet - Practice Coding Problems

Car Fleet - Problem

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer arrays position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car. A car fleet is a single car or a group of cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet. Return the number of car fleets that will arrive at the destination.

Input & Output

Example 1 — Multiple Fleets

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

› Output: 3

💡 Note: Car at position 10 (speed 2) takes 1.0 time. Car at position 8 (speed 4) takes 1.0 time, joining the first fleet. Car at position 5 (speed 1) takes 7.0 time, forming a new fleet. Cars at positions 3 and 0 join existing fleets based on their arrival times.

Example 2 — Single Fleet

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

› Output: 1

💡 Note: Only one car, so it forms one fleet by itself.

Example 3 — No Catching Up

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

› Output: 1

💡 Note: All cars take 25.0, 49.0, and 96.0 time respectively. The fastest car catches up to others, forming one large fleet.

Constraints

n == position.length == speed.length
1 ≤ n ≤ 10⁵
0 < target ≤ 10⁶
0 ≤ position[i] < target
All the values of position are unique
0 < speed[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Cars at different positions with various speeds heading to target

Process

Faster cars catch up to slower ones, forming fleets

Output

Count of distinct car fleets reaching destination

Key Takeaway

🎯 Key Insight: Cars closer to target determine fleet speed - work backwards from finish line!

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Facebook 28

The key insight is that cars closer to the target control fleet formation. The optimal approach sorts cars by position and calculates arrival times: (target - position) / speed. Using a monotonic stack or simple iteration, we count fleets by tracking when arrival times increase. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort by Position + Time Calculation	O(n log n)	O(n)	Calculate arrival time for each car, then determine fleet formation
Brute Force Simulation	O(n × target)	O(n)	Simulate each time step and check if cars merge into fleets
Monotonic Stack Approach	O(n log n)	O(n)	Use stack to track fleet formation by maintaining monotonic arrival times

Sort by Position + Time Calculation — Algorithm Steps

Step 1: Sort cars by starting position (closest to target first)
Step 2: Calculate arrival time for each car: (target - position) / speed
Step 3: Iterate from closest to target, tracking fleet formation
Step 4: A car forms new fleet if it takes longer than car ahead

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Position

Order cars from closest to target to farthest

Calculate Times

Compute arrival time = (target - position) / speed

Count Fleets

New fleet forms when arrival time increases

Code -

solution.c — C

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

typedef struct {
    int pos, spd;
} Car;

int compare(const void *a, const void *b) {
    Car *carA = (Car*)a;
    Car *carB = (Car*)b;
    return carB->pos - carA->pos; // descending order
}

int solution(int target, int* position, int positionSize, int* speed, int speedSize) {
    Car* cars = (Car*)malloc(positionSize * sizeof(Car));
    int n = positionSize;
    
    for (int i = 0; i < n; i++) {
        cars[i].pos = position[i];
        cars[i].spd = speed[i];
    }
    
    qsort(cars, n, sizeof(Car), compare);
    
    int fleets = 0;
    double prevTime = 0;
    
    for (int i = 0; i < n; i++) {
        double timeToTarget = (double)(target - cars[i].pos) / cars[i].spd;
        
        if (timeToTarget > prevTime) {
            fleets++;
            prevTime = timeToTarget;
        }
    }
    
    free(cars);
    return fleets;
}

int main() {
    int target;
    scanf("%d", &target);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int position[1000], speed[1000];
    int posSize = 0, spdSize = 0;
    
    char *ptr = strchr(line, '[') + 1;
    char *token = strtok(ptr, ",]");
    while (token) {
        position[posSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    ptr = strchr(line, '[') + 1;
    token = strtok(ptr, ",]");
    while (token) {
        speed[spdSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(target, position, posSize, speed, spdSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting cars by position dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Store car data and arrival times

⚡ Linearithmic Space

168.4K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort by Position + Time Calculation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler