Difficulty: MediumStack

Car Fleet

Problem in Plain English

Given a target mile marker plus each car starting position and speed, where faster cars queue behind slower ones instead of passing, return how many distinct fleets arrive at the target.

Problem Statement

There are n cars going to the same destination along a one-lane road. You are given the integer target (the destination position), an array position of starting positions, and an array speed of speeds.

A car can never pass the car ahead of it: a faster car catches up and then follows at the slower speed, and cars arriving together count as one fleet. Return the number of car fleets that arrive at the destination. For target = 12 with position = [10,8,0,5,3] and speed = [2,4,1,1,3] the answer is 3.

Constraints

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

Examples

Example 1

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

Positions 10 and 8 meet at target 12 and arrive at time 1. Positions 5 and 3 meet at mile 6; their fleet then travels at speed 1 and arrives at time 7. Position 0 travels alone and arrives at time 12. These three groups give 3 fleets.

Example 2

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

A single car always forms exactly one fleet.

Example 3

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

The rear cars at 0 and 2 first merge at mile 4 after 1 hour. That fleet slows to speed 2, catches the original front car at mile 6 after 2 hours, then slows to speed 1. All three arrive together at time 96, giving 1 fleet.

Example 4

Input: target = 10, position = [8,6], speed = [1,2]
Output: 1

Both solo times are 2. The rear car catches the front car exactly at the destination, and a meeting at the target still counts as one fleet.

Intuition

Cars cannot pass, so traffic order is fixed by starting position. Replace motion with solo arrival time (target - position) / speed. A rear car arriving no later than the fleet immediately ahead catches it by the target and adopts its arrival time. In Example 1 the nearest-first times are [1,1,7,3,12]: 1 joins 1, 3 joins 7, and 12 stays separate. The bottleneck is the nearest existing fleet, whose arrival time is the largest processed time.

Approaches

Pairwise Catch Up

Solution Details

Reveal Pairwise Catch Up: intuition, complexity, and code

Intuition

Keep all established fleet arrival times and test whether a rear car can catch any of them. Nearest-first sorting makes those times strictly increasing. Testing every leader repeats comparisons, but a successful comparison is enough to show the car belongs to some existing fleet; the method counts fleets without assigning a specific leader.

Step-by-Step Logic

Compute every car solo time using floating-point division; Example 1 gives [1,1,12,7,3] in input order.
Sort indices by decreasing position, keeping each speed paired with its car. Example 1 visits indices [0,1,3,4,2], positions [10,8,5,3,0], times [1,1,7,3,12].
Start an empty leader list. For each car, set joins = false and compare its time against each stored leader; stop on time <= leader time. Positions 10 and 8 leave leaders [1].
If no comparison succeeds, append the time as a new fleet. Position 5 appends 7; position 3 fails against 1 but succeeds against 7 and leaves [1,7].
After all cars, return the list length. Position 0 fails against 1 and 7, appends 12, and returns 3.

Why It Works

Induct on cars processed from nearest to farthest. Fleet arrival times in the leaders list grow strictly: a new time is appended only if it exceeds every stored time. Therefore the last leader represents the nearest fleet ahead and the largest arrival time. If the rear car has a solo time no greater than any stored time, it is also no greater than that nearest fleet time, so it catches that fleet by the target. Otherwise it arrives later than the nearest fleet and cannot pass it, so it remains a new fleet. Equal times meet at the target. The loop only tests whether a merge exists; its first successful leader is not necessarily the actual fleet joined.

Dry Run

Pairwise Catch Up: variable states at each step
visit / input index	position / solo time	leaders before	comparisons / joins transition	leaders after	count
0 / 0	10 / 1	[]	joins=false; no leaders	[1]	1
1 / 1	8 / 1	[1]	1 <= 1; false -> true	[1]	1
2 / 3	5 / 7	[1]	7 > 1; stays false	[1,7]	2
3 / 4	3 / 3	[1,7]	3 > 1; 3 <= 7; false -> true	[1,7]	2
4 / 2	0 / 12	[1,7]	12 > 1; 12 > 7; stays false	[1,7,12]	return 3

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

For n cars, sorting costs O(n log n) comparisons under the usual comparison-sort model. When every car forms a fleet, leader checks total n(n - 1)/2, dominating sorting with O(n^2) time. Time, order and leader arrays, plus library sort workspace, use O(n) auxiliary space. Java object-array sorting and Python sorted use up to linear workspace; JavaScript sort implementation costs depend on the engine.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int carFleet(int target, int[] position, int[] speed) {5        int n = position.length;6        double[] time = new double[n];7        Integer[] order = new Integer[n];8        for (int i = 0; i < n; i++) {9            time[i] = (double) (target - position[i]) / speed[i];10            order[i] = i;11        }12        Arrays.sort(order, (a, b) -> Integer.compare(position[b], position[a]));13        List<Double> leaders = new ArrayList<>();14        for (int idx = 0; idx < n; idx++) {15            int i = order[idx];16            boolean joins = false;17            for (int f = 0; f < leaders.size(); f++) {18                if (time[i] <= leaders.get(f)) {19                    joins = true;20                    break;21                }22            }23            if (!joins) {24                leaders.add(time[i]);25            }26        }27        return leaders.size();28    }29}

Hints

Hint 1

For each car compute its solo arrival time as (target - position) / speed: without traffic that is exactly when it would arrive.

Hint 2

A car starting behind joins an ahead fleet exactly when its solo time is less than or equal to that fleet arrival time.

Hint 3

Sort nearest-first. New fleet times grow strictly, so the nearest fleet ahead has the largest time already recorded.

Edge Cases

A single car: nothing can catch it and it catches nothing, so the answer is 1.
Equal solo times for neighbours, such as times 1 and 1: the behind car arrives exactly with the ahead one and they form one fleet.
A very slow car ahead of many fast cars: every fast car catches the same fleet, so the answer stays 1 for the group.
Input positions may be unsorted: keep position and speed paired while sorting; sorting just position invents different cars.
Equal speeds preserve all initial gaps, so every car remains its own fleet.
Several fast rear cars may merge first and then reach a slower front fleet; the final bottleneck time determines their shared arrival.

Common Mistakes and Interview Tips

Using integer division for (target - position) / speed: times like 2.5 truncate and equal-time fleets get miscounted, so use floating-point division.
Sorting farthest-first and scanning forward: the bottleneck logic reads cleanly only nearest-first, where each new fleet time must beat the running maximum.
Starting a new fleet on >= instead of strictly >: an equal time means catching up exactly at the target, which is still one fleet.
Treating the first successful leader comparison as an actual group assignment: the baseline counts only whether a merge occurs; the nearest fleet controls the traffic.
Interview check: explain why only one maximum remains after sorting before claiming the scan is linear; total time still includes sorting.

Key Takeaway

For catch-up processes, sort by position and sweep from the destination outward, letting a single running extreme replace all pairwise comparisons.