Car Fleet

1. Problem & Core Objective

The problem

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

position[i] and speed[i] are the position and speed of the i-th car. A car can never pass another; if it catches up, it slows to match and they travel as a car fleet — a single unit at the slower car's speed.

Return the number of car fleets that arrive at the destination.

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

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

Constraints:

• n == position.length == speed.length
• 1 <= n <= 10^5
• 0 < target <= 10^6
• 0 <= position[i] < target, and all positions are unique
• 0 < speed[i] <= 10^6

What the interviewer is actually testing

This is the least obviously-a-stack problem in the section, which is the point.

1. Can you reduce "catching up" to a comparison? Simulating positions over time is hopeless. The reframe — compare arrival times — collapses the whole physics.
2. Do you sort by position descending? A car can only be blocked by cars ahead of it, so processing front-to-back is what makes a single pass work. Getting the direction backwards is the standard failure.
3. Do you realize the stack is optional? A running maximum of arrival times does the same job in O(1) space. Seeing that is the senior observation.
4. Do you handle the tie correctly? Equal arrival times mean the cars merge, not that they form separate fleets.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5, so O(n log n) is fine and O(n²) (10^10) is not. Sorting is affordable and, as it turns out, essential.

Positions are unique, which removes the awkward case of two cars starting at the same spot.

Step 2 — Don't simulate

The naive mental model is to step time forward and watch cars collide. That's unbounded work and floating-point misery.

The reframe: a car's behaviour is fully determined by when it would arrive if nothing blocked it:

time[i] = (target − position[i]) / speed[i]

That single number captures everything relevant about the car.

Step 3 — Translate "catches up" into a comparison

Suppose car A is ahead of car B (closer to the target). When does B catch A?

• If B's unobstructed arrival time is ≤ A's, B would reach the target no later than A. Since it can't pass, it must have caught up along the way. They merge.
• If B's time is > A's, B is slower and falls further behind. B is a separate fleet.

A car merges into the fleet ahead exactly when its unobstructed arrival time is ≤ that fleet's arrival time.

No simulation, no collision points — one comparison per car.

Step 4 — Process front-to-back

A car can only be blocked by cars ahead of it. So if I process cars in order of decreasing position — nearest the target first — then by the time I evaluate a car, everything that could block it is already resolved.

Sort by position descending.

Ascending would evaluate a car before knowing what's in front of it, which is exactly backwards.

Step 5 — What to compare against

When merging happens, the fleet travels at the slower car's speed — so the fleet's arrival time is the maximum of its members' unobstructed times.

Walking front-to-back, maintain the arrival time of the fleet currently ahead. For each car:

• time > timeOfFleetAhead → it's slower, can't catch up → new fleet, and this becomes the fleet ahead.
• time <= timeOfFleetAhead → it catches up → absorbed, and the fleet's time is unchanged (the car ahead is still the slowest).

Step 6 — Where the stack comes in, and why it's optional

A stack of fleet-leader arrival times makes the "fleet ahead" explicit, and stack.size() is the answer.

But notice: you only ever compare against the top and only ever push values larger than it. So the stack is strictly increasing, and its top is always its maximum. A single maxTime variable does the same job — the stack is expository rather than necessary.

Both are worth presenting; the stack shows the structure, the variable shows you saw through it.

3. Solution Paths

Approach 1 — Brute force pairwise comparison

public int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;
    double[] time = new double[n];
    for (int i = 0; i < n; i++) time[i] = (double)(target - position[i]) / speed[i];

    int fleets = 0;
    for (int i = 0; i < n; i++) {
        boolean isLeader = true;
        for (int j = 0; j < n; j++) {                       // is any car ahead slower?
            if (position[j] > position[i] && time[j] >= time[i]) { isLeader = false; break; }
        }
        if (isLeader) fleets++;
    }
    return fleets;
}

How it works. A car leads a fleet if no car ahead of it arrives at the same time or later — because such a car would block it.

• Time: O(n²).
• Space: O(n).

Counter-questions on this approach

⭐ "What are you recomputing for each car?"

The same forward scan, over and over. Whether car i is blocked depends only on the slowest car ahead of it — a running maximum. Computing that once while walking front-to-back replaces the entire inner loop.

"Is the >= in time[j] >= time[i] correct, or should it be >?"

>= is right. If a car ahead has exactly the same arrival time, the car behind reaches the target at the same moment and is part of that fleet, not a separate one. Using > would count merging cars as distinct fleets. It's the tie case, and it's easy to get wrong.

Approach 2 — Sort, then stack (optimal)

public int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;

    int[][] cars = new int[n][2];
    for (int i = 0; i < n; i++) cars[i] = new int[]{position[i], speed[i]};
    Arrays.sort(cars, (a, b) -> b[0] - a[0]);              // DESCENDING by position

    Deque<Double> stack = new ArrayDeque<>();              // arrival times of fleet leaders
    for (int[] car : cars) {
        double time = (double)(target - car[0]) / car[1];
        if (stack.isEmpty() || time > stack.peek()) {
            stack.push(time);                              // slower than the fleet ahead → new fleet
        }
        // otherwise it catches up and is absorbed — push nothing
    }
    return stack.size();
}

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

Sorted descending by position:

Answer: 3 ✓

Notice the car at position 3 (time 3.0): it's faster than the fleet ahead (7.0), so it catches up and merges — even though 3.0 < 7.0 might look like it should arrive first. It can't pass, so it's capped at 7.0.

• Time: O(n log n) — dominated by the sort.
• Space: O(n) — the pairs array and the stack.

Counter-questions on this approach

⭐ "Why sort descending by position? What breaks with ascending?"

A car can only be blocked by cars ahead of it — closer to the target. Sorting descending means that when I evaluate a car, everything that could block it has already been processed and reduced to a single "fleet ahead" arrival time.

Ascending would evaluate a car before knowing what's in front of it, so I'd have no basis for the comparison. It's not a slower variant — it's simply wrong, and it's the most common failure in this problem.

⭐ "You compare with > rather than >=. Why does the tie merge rather than split?"

Because two cars arriving at the same time are travelling together at that moment — that's one fleet, not two. In the trace, the cars at positions 10 and 8 both arrive at time 1.0, and they count once.

Using >= would push a new fleet on the tie and return 4 instead of 3. Verified — it's the case that distinguishes a correct solution.

"Why double for the arrival times? Could floating point cause a wrong answer?"

It's a genuine concern. Times are ratios up to 10^6 / 1, and double has 53 bits of mantissa — far more than enough for these magnitudes, so exact ties like 1.0 versus 1.0 compare correctly here.

To avoid floating point entirely I could compare fractions by cross-multiplication: (target − p₁) · s₂ versus (target − p₂) · s₁, using long to hold products up to 10^12. That's exact. I'd mention it as the robust alternative — it's the right instinct whenever equality of ratios matters.

"Is the Deque<Double> doing anything a counter couldn't?"

Not really, and that's worth noticing. I only ever compare against the top and only ever push values greater than it, so the stack is strictly increasing and its top is always its maximum. A single maxTime variable would do the same work in O(1) space — the stack makes the "fleet leader" semantics visible but isn't load-bearing.

"(a, b) -> b[0] - a[0] — is that comparator safe?"

Here yes, because positions are bounded by 10^6, so the subtraction can't overflow. In general a subtraction comparator wraps when values straddle the int range and silently corrupts the sort. I'd write Integer.compare(b[0], a[0]) by habit. See 04.

Approach 3 — Sort, then a running maximum

public 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]);      // DESCENDING by position

    int fleets = 0;
    double maxTime = 0;
    for (int i : idx) {
        double time = (double)(target - position[i]) / speed[i];
        if (time > maxTime) {          // slower than everything ahead → its own fleet
            fleets++;
            maxTime = time;
        }
    }
    return fleets;
}

How it works. Identical logic, with maxTime replacing the stack. Since the stack was strictly increasing and only its top was ever read, one variable suffices.

• Time: O(n log n).
• Space: O(n) for the index array — O(1) beyond the sort if you're allowed to sort the inputs in place.

Counter-questions on this approach

⭐ "If this is simpler and uses less space, why is the stack version worth knowing?"

Because the stack makes the reasoning visible — each entry is a fleet leader, and stack.size() is literally the answer. That's easier to explain and to verify. Once you notice the stack only ever grows at the top and only the top is read, collapsing it to a variable is a mechanical step.

I'd present the stack first to show the structure, then offer this. Arriving at the variable directly, without explaining the fleet-leader idea, is harder to follow.

"Why Integer[] rather than int[] for the indices?"

Because Arrays.sort(int[], Comparator) doesn't exist — comparators work on objects, and int is a primitive. Sorting indices by an external key requires boxing. The alternative is building int[][] pairs as in Approach 2, which sorts fine because its elements are int[] objects. See 04 §5.1.

"Does maxTime starting at 0 cause any problem?"

No, because every car has a strictly positive arrival time: position[i] < target guarantees a positive numerator, and speed[i] > 0 a positive denominator. So the first car always satisfies time > 0 and correctly starts a fleet. Worth checking against the constraints rather than assuming.

Comparison

4. Why the Optimal Wins

Against brute force. Whether a car is blocked depends only on the slowest car ahead of it — a running maximum. The brute force recomputes that scan for every car; sorting once and sweeping computes it incrementally.

Why sorting is the enabling step, not an overhead. The comparison "does this car catch the one ahead" is only meaningful once you know what is ahead. Sorting creates the order the sweep then exploits — and at O(n log n) it dominates the O(n) sweep, making it the whole cost of the algorithm rather than a preliminary.

Stack vs running maximum. Identical complexity. Say the honest thing:

"The stack makes the fleet-leader structure explicit, which is easier to reason about and to explain. But since it's strictly increasing and I only read the top, a single variable does the same job. I'd write the stack to demonstrate the idea, then note it collapses."

Why O(n log n) is the floor. The answer depends on the relative order of cars by position, and no comparison-based method can establish that order faster than O(n log n). Without the ordering there's no notion of "ahead", so sorting isn't optional.

The transferable idea:

When the interaction between elements depends on their order, sort first — then a single sweep with a running aggregate replaces all the pairwise comparisons.

The same shape appears throughout Intervals (§16), where sorting by start or end time turns overlap detection into a linear scan.

5. Java Prerequisites

Sorting 2-D arrays with a comparator

int[][] cars = new int[n][2];
Arrays.sort(cars, (a, b) -> b[0] - a[0]);                        // descending by column 0
Arrays.sort(cars, Comparator.comparingInt((int[] c) -> -c[0]));  // overflow-safe alternative

int[][] sorts with a comparator because its elements are int[] objects. A flat int[] cannot — there is no Arrays.sort(int[], Comparator) overload. That asymmetry is why Approach 3 needs Integer[].

Integer division vs floating point

(target - car[0]) / car[1]                 // INTEGER division — truncates, WRONG here
(double)(target - car[0]) / car[1]         // correct

Without the cast, (12 - 8) / 4 gives 1 and (12 - 10) / 2 gives 1 — which happens to be right — but (12 - 5) / 2 would give 3 instead of 3.5, merging cars that shouldn't merge. The cast goes on the numerator, before the division.

Exact comparison without floating point

// "does car A arrive no later than car B?"
// (target - pA)/sA  <=  (target - pB)/sB
// cross-multiply (both speeds positive, so the inequality direction is preserved):
(long)(target - pA) * sB <= (long)(target - pB) * sA

Products reach 10^6 × 10^6 = 10^12, which needs long. Cast before multiplying, not after — (long)(a * b) would overflow in int first. See 03.

ArrayDeque<Double> and autoboxing

Deque<Double> stack = new ArrayDeque<>();
stack.push(time);               // double → Double
time > stack.peek()             // Double auto-unboxed for the comparison

The relational comparison unboxes safely. Never use == on two Double objects — it compares references. (And == on primitive doubles is also unreliable for computed values, which is another argument for the cross-multiplication form.)

Pairing values before sorting

int[][] cars = new int[n][2];
for (int i = 0; i < n; i++) cars[i] = new int[]{position[i], speed[i]};

position and speed are parallel arrays; sorting one would desynchronize them. Pairing first keeps each car's data together — the same technique as sorting indices in Minimum Interval to Include Each Query.

6. Interview Communication Guide

Clarifying questions

1. "Can cars pass each other?" — no, which is the entire premise. If they could, every car would be its own fleet.
2. "What happens when a car catches another exactly at the destination?" — they count as one fleet. This is the > versus >= decision.
3. "Can two cars start at the same position?" — the constraints say positions are unique, which removes an awkward case.
4. "Is a single car a fleet?" — yes, so n = 1 returns 1.
5. "Can I use floating point, or do you want exact arithmetic?" — worth asking; the cross-multiplication form avoids it entirely.

The pitch

"Simulating the cars moving would be hopeless. The reframe is that each car is fully described by when it would arrive if nothing blocked it: (target − position) / speed.

Then 'catches up' becomes a comparison. If a car behind would arrive no later than the car ahead, it must have caught up along the way — so they merge. If it would arrive later, it's slower and stays separate.

A car can only be blocked by cars ahead of it, so I sort by position descending and sweep front-to-back. That way, by the time I evaluate a car, everything that could block it is already resolved into a single 'fleet ahead' arrival time.

For each car: if its time is greater than the fleet ahead's, it's slower and forms a new fleet. Otherwise it's absorbed. I'll keep a stack of fleet-leader times, and stack.size() is the answer.

The tie matters — equal arrival times mean the cars are travelling together, so that's one fleet. I compare with strict >.

O(n log n) for the sort, then a linear sweep.

One observation: the stack only ever grows at the top and I only read the top, so it's strictly increasing and a single maxTime variable would do the same job. I'd write the stack because it makes the fleet-leader structure visible, but it collapses.

On floating point — the ratios are well within double precision here, but if exactness mattered I'd cross-multiply with long instead of dividing."

Edge cases to raise proactively

The tie case is the one to volunteer. In the showcase input, the cars at positions 10 and 8 both arrive at time 1.0 — and they are one fleet. A solution using >= returns 4 instead of 3.

"All same speed → n fleets" is a good sanity check: if nobody is faster than anybody, no car ever catches another, so every car arrives independently.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Return the arrival time of the last fleet, not the count."

That's the maximum arrival time over all cars — no sorting or sweeping needed at all, just one pass taking the max of (target − position) / speed. O(n). It's a nice illustration that a small change to the output can collapse the algorithm entirely: the fleet structure was only needed to count fleets, not to find when everyone has arrived.

"What if cars could pass each other?"

Then no car ever blocks another, and each arrives independently — the answer is always n. Worth stating plainly, since it shows the no-passing rule is what creates the whole problem.

"What if positions weren't unique — two cars starting at the same spot?"

Physically ambiguous, so I'd clarify the intended semantics. The reasonable reading is that co-located cars are already together, so the slower one dictates. In code: sort by position descending with ties broken by speed ascending, and the existing logic handles it, since the slower car is evaluated first and the faster one is absorbed.

"What if the road had multiple lanes — cars can pass if a lane is free?"

Fundamentally different; the fleet abstraction breaks because blocking is no longer determined by position order alone. It becomes a scheduling problem, and I'd want to understand the passing rules precisely before proposing anything.

"What if cars were added incrementally and you had to report the fleet count after each addition?"

The sorted sweep no longer works, since a new car can be inserted anywhere and change the structure. A TreeMap keyed by position lets you find the neighbours in O(log n) and determine whether the new car merges, splits, or starts a fleet — with careful bookkeeping of fleet boundaries. O(log n) per insertion. See 02 §3.

"What if you needed which cars are in each fleet, not just the count?"

The stack version extends naturally: instead of pushing just the arrival time, push a list of member indices, appending to the top fleet's list when a car is absorbed. Same O(n log n) time; space becomes O(n) for the membership lists.

"Avoid floating point entirely."

Compare ratios by cross-multiplication: car B catches fleet A when (target − pB) · sA <= (target − pA) · sB. Products reach 10^12, so use long. Exact, no precision concerns, and the right default whenever equality of ratios decides the answer.