Start learning free

LESSON 415 OF 572 · STACK

Car Fleet in C#: O(n log n) with Sorting and a Stack

Practice O(n log n) Read the full explanation

There are n cars on a one-lane road, all driving to the same destination, target miles from the start of the road. You are given two arrays of n integers, position and speed: car i starts at mile position[i] and drives at speed[i] miles per hour.

A car can never pass the car ahead of it. When it catches up with a slower car, it slows down and the two drive on together, bumper to bumper, at the speed of the car in front. A car fleet is a group of cars driving together like this; a car that drives alone is a fleet too. A car that catches up with a fleet exactly at target is part of that fleet.

Return the number of car fleets that arrive at target.

 

Example 1:

Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Explanation:
- The car from mile 10 would arrive after (12 - 10) / 2 = 1 hour, and so would the car from mile 8,
  after (12 - 8) / 4 = 1 hour. The second one catches up with the first exactly at the target: one fleet.
- The car from mile 5 (speed 1) would need 7 hours, the car from mile 3 (speed 3) only 3. They meet at
  mile 6 after 1 hour and drive on together at speed 1: a second fleet, arriving after 7 hours.
- The car from mile 0 (speed 1) would need 12 hours and never catches up with anyone: a third fleet.

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: A single car is one fleet.

Example 3:

Input: target = 100, position = [0, 2, 4], speed = [4, 2, 1]
Output: 1
Explanation: The car from mile 0 catches up with the car from mile 2 at mile 4, after 1 hour,
and they drive on at speed 2. That fleet catches up with the car from mile 4 at mile 6, after 2 hours, and
all three drive on at speed 1, arriving together after 96 hours.

 

Constraints:

  • n is the length of both position and speed
  • 1 <= n <= 105
  • 1 <= target <= 106
  • 0 <= position[i] < target
  • All the values in position are different.
  • 1 <= speed[i] <= 106

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.



Only the order of the cars on the road matters, so visit them from the one closest to the target to the one farthest from it. If nothing slowed it down, car i would arrive after (target - position[i]) / speed[i] hours. A car that would arrive no later than the fleet just ahead of it catches up with that fleet, at the latest at the target, and joins it. A car that would arrive later never catches up: it starts a new fleet, which the cars behind it may join.

Keep the fleets found so far on a stack. A fleet arrives when the car that leads it would arrive on its own, since that car was never slowed down. The fleet just ahead of the next car is always the one on top of the stack, and it is also the one that arrives last: compare the car with it only. A car that would arrive later starts a new fleet and goes on top; otherwise it joins the top fleet. The answer is the size of the stack.

The times are fractions. Compare them exactly, without dividing: since the speeds are positive, (target - p1) / s1 > (target - p2) / s2 is the same as (target - p1) * s2 > (target - p2) * s1. These products can reach 1012, more than a 32-bit integer holds: where integers are 32 bits, compute them with 64-bit integers. A Python integer, or a JavaScript or TypeScript number (exact for whole numbers below 253), holds them as it is.

Sorting the cars by position takes O(n log n) time. The pass over the sorted cars does a constant amount of work for each car, so sorting is the larger part. The sorted order and the stack hold at most n cars each: O(n) extra space.
STEP 1 OF 12
    Ctrl + Enter to check

    C# · STACK

    Car Fleet in C#, explained

    Problem overview

    The method CarFleet receives the target mile of a one-lane road and two int[] arrays: position[i] is the mile where car i starts, and speed[i] its speed in miles per hour. Cars can't pass each other. A car that catches up with a slower car or fleet ahead of it slows down and drives on with it, bumper to bumper. A group of cars driving together is a fleet, and a lone car is a fleet too. A car that reaches a fleet exactly at target is part of it. The method returns how many fleets arrive.

    In the first example, target = 12, position = {10, 8, 0, 5, 3} and speed = {2, 4, 1, 1, 3}. The cars from miles 10 and 8 both arrive after 1 hour (the second catches the first exactly at the target): one fleet. The car from mile 3 catches the car from mile 5, and they drive on at speed 1: a second fleet. The car from mile 0 never catches anyone: a third. The answer is 3.

    Approach: sort by position, then compare arrival times

    Only the order of the cars on the road matters. Visit them from the one closest to the target to the one farthest from it. Driving alone and unblocked, car i would arrive after (target - position[i]) / speed[i] hours. The car closest to the target can never be blocked, so it leads the first fleet.

    For every later car, look at the fleet just ahead of it. A fleet arrives when its leading car would arrive alone, since that car is never slowed down. If the new car would arrive no later than that, it catches up with the fleet at the latest at the target, and joins it. If it would arrive later, it never catches up, so it starts a new fleet, which the cars behind it may still join.

    The fleet just ahead is always the most recent one, so a stack of fleets is enough: compare each car with the top only. Each fleet is stored as the number of the car that leads it. The answer is the size of the stack.

    Here is what happens for the first example. The cars are visited in the order 0, 1, 3, 4, 2:

    car 0 (mile 10, speed 2) alone: 1 h -> new fleet, fleets=1
car 1 (mile 8, speed 4) alone: 1 h -> joins, fleets=1
car 3 (mile 5, speed 1) alone: 7 h -> new fleet, fleets=2
car 4 (mile 3, speed 3) alone: 3 h -> joins, fleets=2
car 2 (mile 0, speed 1) alone: 12 h -> new fleet, fleets=3

    Car 4 would arrive after 3 hours, earlier than the 7 hours of the fleet ahead, so it joins. Car 1 ties with car 0 at 1 hour and joins as well: arriving at the same moment still means one fleet, so the comparison must be strict.

    Step by step

    1. Store the number of cars, position.Length, in n.
    2. Create order, an int[] of size n. It will hold car numbers sorted by position. Sorting the numbers, not the positions, keeps each position together with its speed.
    3. Fill it with a loop: order[i] = i.
    4. Sort it with Array.Sort(order, (a, b) => position[b] - position[a]). The lambda gets two car numbers and returns a negative number when car a must come first. That happens when a has the larger position, so the car closest to the target comes first.
    5. Create the stack fleets, a Stack<int> of lead-car numbers.
    6. Visit the cars in sorted order with foreach.
    7. Start a new fleet when the stack is empty or the car would arrive later than the fleet on top: fleets.Count == 0 || ArrivesLater(...). The || stops at the first true part, so Peek() is only called on a non-empty stack. Otherwise do nothing: the car joins the top fleet.
    8. Push the car with fleets.Push(car).
    9. Return fleets.Count. Every car either started a fleet or joined one, so each fleet is on the stack once.
    10. Write the helper ArrivesLater, which answers whether car, driving alone, would arrive strictly later than lead.
    11. Compare without dividing. The time of car is greater than the time of lead exactly when (target - position[car]) * speed[lead] is greater than (target - position[lead]) * speed[car]. Both speeds are positive, so multiplying both sides by them keeps the comparison the same. The products are computed in 64 bits.

    The solution in C#

    class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        int[] order = new int[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Array.Sort(order, (a, b) => position[b] - position[a]);
        Stack<int> fleets = new Stack<int>();
        foreach (int car in order) {
            if (fleets.Count == 0 || ArrivesLater(target, position, speed, car, fleets.Peek())) {
                fleets.Push(car);
            }
        }
        return fleets.Count;
    }

    bool ArrivesLater(int target, int[] position, int[] speed, int car, int lead) {
        return (long) (target - position[car]) * speed[lead] > (long) (target - position[lead]) * speed[car];
    }
}

    The C# details worth knowing:

    • Why (long). target - position[car] can be close to 1,000,000 and a speed can be 1,000,000, so a product can reach 10^12, far beyond what an int holds (about 2.1 billion). In C#, the type of a multiplication comes from its operands: int * int is computed in 32 bits and wraps silently. With a = 1000000 and b = 1000000, a * b gives -727379968, while (long) a * b gives 1000000000000. The cast applies to the first factor and makes the whole multiplication 64-bit, because the other factor is widened automatically.
    • The cast must come before the multiplication. long product = a * b; still multiplies as ints and widens the wrapped result afterwards: it also prints -727379968. Cast an operand, not the result.
    • The wrapped version gives wrong answers. For target = 1000000, position = {0, 1} and speed = {1, 1000000}, the method returns 2 with long products and 1 if the same comparison is written with plain ints.
    • Array.Sort with a lambda. The overload Array.Sort(array, comparison) takes a Comparison<T>, which a lambda (a, b) => ... converts to. The lambda returns a negative number, zero or a positive number. Subtracting positions is safe here, because positions are between 0 and 10^6. With values near int.MinValue or int.MaxValue, a subtraction could overflow, and CompareTo would be the safe choice.
    • The lambda uses the method's arrays. It reads position from the enclosing method (a closure), which is how the sort orders car numbers by a value stored elsewhere.
    • The helper is private. A method written without an access modifier is private in a class, which is enough here, since only CarFleet calls it.
    • Stack<T> comes with Push, Peek (look at the top without removing it), Pop and Count. It lives in System.Collections.Generic, and Array in System: in a file of your own, add both using lines.

    Complexity

    Time: O(n log n). Sorting the cars takes O(n log n). The loop after it does a constant amount of work per car, O(n) in total, so sorting dominates.

    Space: O(n). The order array and the stack each hold at most n cars.

    Edge cases and common mistakes

    • One car. target = 10, position = {3}, speed = {3} gives 1.
    • Cars given out of order. The input isn't sorted by position. position = {0, 4, 2} with speed = {2, 1, 3} and target = 10 gives 1; the sort makes the visiting order right.
    • Same arrival time. A strict > in the comparison keeps cars that tie with the fleet ahead in that fleet. Using >= would split the example above into more fleets.
    • A faster car behind a slower one. target = 100, position = {0, 2, 4}, speed = {4, 2, 1} gives 1: the cars merge one after another and all arrive together.
    • A slower car behind. target = 10, position = {0, 5}, speed = {1, 1} gives 2: the car behind never catches up. With speed = {10, 1} it gives 1.
    • Dividing integers. (target - position) / speed with ints truncates, so 10 / 3 becomes 3 and two different arrival times can look equal. Dividing as double avoids that for most inputs, but comparing products is exact.
    • Sorting the positions alone. Positions and speeds would no longer match. Sorting car numbers keeps each car's two values together.
    • Comparing with the wrong fleet. A car must be compared with the fleet on top of the stack, not with the car just before it in the order: a car that joined a fleet is no longer the one that sets its arrival time.

    Testing

    • target = 12, position = {10, 8, 0, 5, 3}, speed = {2, 4, 1, 1, 3} gives 3.
    • target = 10, position = {3}, speed = {3} gives 1.
    • target = 100, position = {0, 2, 4}, speed = {4, 2, 1} gives 1.
    • target = 10, position = {0, 4, 2}, speed = {2, 1, 3} gives 1.
    • target = 10, position = {6, 8}, speed = {3, 2} gives 2.
    • target = 10, position = {0, 5}, speed = {1, 1} gives 2.
    • target = 1000000, position = {0, 1}, speed = {1, 1000000} gives 2.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free