Car Fleet

Medium
76.

Car Fleet

Car Fleet is a medium coding problem on arrays, sorting and stack, asked in Nutanix interviews.

n cars head to a destination target miles away. Car i starts at position[i] (all distinct) with speed speed[i]. A faster car that catches up to a slower one slows to match it, forming a fleet. A car that catches a fleet exactly at the target still counts as the same fleet.

Return the number of fleets that arrive.

Example 1

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

Example 2

Input
target = 10, position = [3], speed = [3]
Output
1

Example 3

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

Constraints

  • 1 <= position.length == speed.length <= 25
  • 0 <= position[i] < target <= 1000 (distinct)
  • 1 <= speed[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function(target, position, speed) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Car Fleet — Solution in Python, Java & C++

Car Fleet solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Nutanix.

Car Fleet is a medium coding problem on arrays, sorting and stack, asked in Nutanix interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Stack, Monotonic Stack
  • Asked at: Nutanix
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

n cars head to a destination target miles away. Car i starts at position[i] (all distinct) with speed speed[i]. A faster car that catches up to a slower one slows to match it, forming a fleet. A car that catches a fleet exactly at the target still counts as the same fleet.

Return the number of fleets that arrive.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 1 <= position.length == speed.length <= 25
  • 0 <= position[i] < target <= 1000 (distinct)
  • 1 <= speed[i] <= 100

Hints for Car Fleet

  1. Hint 1

    Sort by starting position (closest to target first) and compute each car's arrival time.

  2. Hint 2

    Scan: a car whose time exceeds the current lead time starts a new fleet.

How to solve Car Fleet

Cars never overtake — a faster car that catches a slower one is stuck behind it forever. So the only thing that decides the answer is arrival time: if a car would reach the target no later than the car ahead of it, it never arrives separately, it merges. Work from the car closest to the target backwards and the whole problem collapses into a single sweep.

Approach

  1. For each car compute the time it would take alone: (target - position[i]) / speed[i].
  2. Sort the cars by starting position, closest to the target first. That is the order they appear on the road, front to back.
  3. Sweep front to back keeping lead — the arrival time of the fleet currently ahead.
  4. If the current car's time is greater than lead, nothing ahead can hold it up, so it starts a new fleet: count it and set lead to its time.
  5. Otherwise it catches the fleet in front and merges — lead is unchanged, because the fleet still moves at the pace of its slowest car.

Why it works

Because cars cannot pass, a car merges into the fleet ahead exactly when its solo arrival time is no later than that fleet's. Sweeping front to back, lead always holds the arrival time of the slowest car ahead of the current one, and that is precisely the car that would block it. Every time we see a strictly larger time we have found a car nothing ahead can slow down — a new fleet — so the count is exact.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Use floating-point (or cross-multiplied) division for the arrival time. Integer division rounds distinct arrival times together and merges fleets that really do arrive apart.
  • A car that catches a fleet exactly at the target counts as the same fleet, so the new-fleet test is a strict >, not >=.
  • Sort by position, not by input order — the input is not given along the road.

Reference solution

Python

from typing import List

def carFleet(target: int, position: List[int], speed: List[int]) -> int:
    cars = sorted(zip(position, speed), key=lambda c: -c[0])
    fleets = 0
    lead = -1.0
    for p, s in cars:
        time = (target - p) / s
        if time > lead:
            fleets += 1
            lead = time
    return fleets

Java

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;
    Arrays.sort(idx, (a, b) -> position[b] - position[a]);
    int fleets = 0;
    double lead = -1.0;
    for (int k = 0; k < n; k++) {
        int j = idx[k];
        double time = (double) (target - position[j]) / speed[j];
        if (time > lead) {
            fleets++;
            lead = time;
        }
    }
    return fleets;
}

C++

int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int n = position.size();
    vector<pair<int, double>> cars;
    for (int i = 0; i < n; i++) {
        cars.push_back(make_pair(position[i], (double) (target - position[i]) / speed[i]));
    }
    sort(cars.begin(), cars.end(), [](const pair<int, double>& a, const pair<int, double>& b) {
        return a.first > b.first;
    });
    int fleets = 0;
    double lead = -1.0;
    for (int i = 0; i < n; i++) {
        if (cars[i].second > lead) {
            fleets++;
            lead = cars[i].second;
        }
    }
    return fleets;
}

JavaScript

var carFleet = function(target, position, speed) {
    const cars = position
        .map(function(p, i) { return { p: p, time: (target - p) / speed[i] }; })
        .sort(function(a, b) { return b.p - a.p; });
    let fleets = 0, lead = -1;
    for (const c of cars) {
        if (c.time > lead) {
            fleets++;
            lead = c.time;
        }
    }
    return fleets;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms