Most Profit Assigning Work

Description

There are n cars on a one-lane road, each starting at a different position and traveling toward a common destination at mile target. You are given two arrays: position (the starting mile of each car) and speed (the speed of each car in miles per hour).

A car can never pass another car ahead of it. When a faster car catches up to a slower car (or a fleet of cars), they merge into a single fleet and continue at the speed of the slowest car in that fleet.

A car fleet is either a single car or a group of cars driving side by side at the same speed. If a car catches up to a fleet right at the target mile, it is still considered part of that fleet.

Return the total number of distinct car fleets that will arrive at the destination.

Examples

Example 1

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

Output: 3

Explanation:

Car at position 10 (speed 2) takes (12 - 10) / 2 = 1.0 hour to reach target.
Car at position 8 (speed 4) takes (12 - 8) / 4 = 1.0 hour to reach target.
Since the car at 8 reaches the car at 10 exactly at the target, they form one fleet.
Car at position 5 (speed 1) takes (12 - 5) / 1 = 7.0 hours. Car at position 3 (speed 3) takes (12 - 3) / 3 = 3.0 hours. Car at 3 catches car at 5 (at mile 6) and they form a fleet, continuing at speed 1.
Car at position 0 (speed 1) takes (12 - 0) / 1 = 12.0 hours. No car behind it to catch up.
Three fleets arrive at the target: {10, 8}, {5, 3}, and {0}.

Example 2

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

Output: 1

Explanation: There is only one car, so it forms a single fleet by itself.

Example 3

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

Output: 1

Explanation:

Car at position 4 (speed 1) takes (100 - 4) / 1 = 96 hours.
Car at position 2 (speed 2) takes (100 - 2) / 2 = 49 hours. It catches the car at 4 (at mile 6) and forms a fleet at speed 1.
Car at position 0 (speed 4) takes (100 - 0) / 4 = 25 hours. It catches the fleet (now moving at speed 1) and joins them.
All three cars ultimately merge into one fleet.

Constraints

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

Editorial

Brute Force

Intuition

The most direct approach is to simulate what actually happens on the road. For each car, compute how long it would take to reach the target if it were driving alone — this is its "ideal arrival time." Then, sort the cars by their starting position (closest to the target first) and scan from front to back.

The key observation is: a car behind another car cannot arrive at the target earlier than the car in front of it (because it cannot pass). If a rear car's ideal arrival time is less than or equal to the car ahead of it, the rear car will catch up and merge into the same fleet. Otherwise, it forms a new fleet.

Think of cars on a highway approaching a toll booth. Faster cars behind slower ones will eventually get stuck behind them. Each "cluster" of cars that gets stuck together becomes one fleet.

Step-by-Step Explanation

Let's trace with target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3].

Step 1: Compute ideal arrival time for each car:

Car at position 10, speed 2: time = (12 - 10) / 2 = 1.0
Car at position 8, speed 4: time = (12 - 8) / 4 = 1.0
Car at position 0, speed 1: time = (12 - 0) / 1 = 12.0
Car at position 5, speed 1: time = (12 - 5) / 1 = 7.0
Car at position 3, speed 3: time = (12 - 3) / 3 = 3.0

Step 2: Sort cars by position descending (closest to target first):

(pos=10, time=1.0), (pos=8, time=1.0), (pos=5, time=7.0), (pos=3, time=3.0), (pos=0, time=12.0)

Step 3: Scan through the sorted cars and count fleets:

Start: fleets = 0, current_max_time = 0
Car at pos=10, time=1.0: time (1.0) > current_max_time (0)? Yes → new fleet! fleets = 1, current_max_time = 1.0
Car at pos=8, time=1.0: time (1.0) > current_max_time (1.0)? No → merges into previous fleet.
Car at pos=5, time=7.0: time (7.0) > current_max_time (1.0)? Yes → new fleet! fleets = 2, current_max_time = 7.0
Car at pos=3, time=3.0: time (3.0) > current_max_time (7.0)? No → merges (catches up to the pos=5 fleet).
Car at pos=0, time=12.0: time (12.0) > current_max_time (7.0)? Yes → new fleet! fleets = 3, current_max_time = 12.0

Result: 3 fleets.

Brute Force — Sort by Position and Count Fleets — Watch how we sort cars by position (closest to target first), compute arrival times, and count new fleets whenever a car's time exceeds the current fleet's time.

Algorithm

For each car i, compute the ideal arrival time: time[i] = (target - position[i]) / speed[i]
Pair each car as (position[i], time[i]) and sort by position in descending order (closest to target first)
Initialize fleets = 0 and max_time = 0
For each car in sorted order:
- If its time > max_time: it forms a new fleet. Increment fleets, update max_time = time
- Otherwise: it merges into the current fleet (no action needed)
Return fleets

Code

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        
        // Pair (position, arrival_time) and sort by position descending
        vector<pair<int, double>> cars(n);
        for (int i = 0; i < n; i++) {
            cars[i] = {position[i], (double)(target - position[i]) / speed[i]};
        }
        sort(cars.begin(), cars.end(), [](auto& a, auto& b) {
            return a.first > b.first;
        });
        
        int fleets = 0;
        double maxTime = 0;
        
        for (auto& [pos, time] : cars) {
            if (time > maxTime) {
                fleets++;
                maxTime = time;
            }
        }
        
        return fleets;
    }
};

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        n = len(position)
        
        # Pair (position, arrival_time) and sort by position descending
        cars = []
        for i in range(n):
            time = (target - position[i]) / speed[i]
            cars.append((position[i], time))
        
        cars.sort(key=lambda x: -x[0])
        
        fleets = 0
        max_time = 0
        
        for pos, time in cars:
            if time > max_time:
                fleets += 1
                max_time = time
        
        return fleets

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        
        // Pair (position, arrival_time)
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }
        
        // Sort by position descending
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
        
        int fleets = 0;
        double maxTime = 0;
        
        for (double[] car : cars) {
            if (car[1] > maxTime) {
                fleets++;
                maxTime = car[1];
            }
        }
        
        return fleets;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Computing arrival times takes O(n). Sorting the cars by position takes O(n log n). The single scan to count fleets takes O(n). The dominant term is O(n log n) from the sort.

Space Complexity: O(n)

We create an auxiliary array of n (position, time) pairs. The sort may also use O(log n) stack space internally.

Why This Approach Is Not Efficient

Actually, the sort-and-scan approach above already runs in O(n log n), which is optimal for this problem since we must process all n cars and sorting is a lower bound for comparison-based ordering. The scan after sorting is O(n).

However, this approach does not use a stack, which is a common pattern for this problem type. The scan-with-max approach works correctly but doesn't generalize as well to variations (like Car Fleet II where you need to track which car catches which). The stack-based approach provides a clearer mental model of fleet formation and is more extensible.

The key question is: can we make the fleet-counting logic more explicit and adaptable? A monotonic stack gives us exactly that — it maintains a record of active fleet leaders and their arrival times, making the merging process visible.

Optimal Approach - Sort and Monotonic Stack

Intuition

The core insight is: a car can only be blocked by cars that are ahead of it (closer to the target). If we process cars from closest to farthest (sorted by position descending), we can determine fleet membership in a single pass.

For each car, compute its time to reach the target if it were driving alone: time = (target - position) / speed. This "ideal arrival time" tells us everything:

If a car behind has an ideal time ≤ the car in front of it, it means the behind car is fast enough to catch the front car before reaching the target. They merge into one fleet, and the fleet travels at the slower car's time (which is the larger time).
If a car behind has an ideal time > the car in front, it is too slow to catch up. It starts a new fleet.

We use a stack to track the arrival times of fleet leaders (the slowest car in each fleet). When processing a new car:

If its time ≤ the stack top, it merges with the fleet represented by the stack top (do nothing — it's absorbed).
If its time > the stack top, it cannot catch any fleet ahead. Push its time as a new fleet leader.

The final stack size equals the number of distinct fleets.

Think of it like a funnel: the slowest cars act as bottlenecks. Every faster car behind them gets trapped. The number of bottlenecks is the number of fleets.

Diagram showing 5 cars on a road with their positions, speeds, and arrival times, illustrating how they form 3 fleets

Step-by-Step Explanation

Let's trace with target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3].

Step 1: Compute arrival times and sort by position descending:

Sorted: [(pos=10, t=1.0), (pos=8, t=1.0), (pos=5, t=7.0), (pos=3, t=3.0), (pos=0, t=12.0)]

Step 2: Initialize empty stack.

Step 3: Process car at pos=10, time=1.0. Stack is empty. Push 1.0.

Stack: [1.0]

Step 4: Process car at pos=8, time=1.0. Stack top = 1.0. Is 1.0 > 1.0? No → car at 8 catches fleet at 10. Do not push (merged into existing fleet).

Stack: [1.0]

Step 5: Process car at pos=5, time=7.0. Stack top = 1.0. Is 7.0 > 1.0? Yes → car at 5 is too slow to catch the fleet ahead. Push 7.0 (new fleet leader).

Stack: [1.0, 7.0]

Step 6: Process car at pos=3, time=3.0. Stack top = 7.0. Is 3.0 > 7.0? No → car at 3 catches the fleet led by pos=5. Merged.

Stack: [1.0, 7.0]

Step 7: Process car at pos=0, time=12.0. Stack top = 7.0. Is 12.0 > 7.0? Yes → car at 0 forms its own fleet. Push 12.0.

Stack: [1.0, 7.0, 12.0]

Result: Stack has 3 entries → 3 fleets.

Monotonic Stack — Tracking Fleet Leaders by Arrival Time — Watch how we process cars from closest to farthest from the target. Each stack entry represents an active fleet leader's arrival time. Slower cars behind push new entries; faster cars behind get absorbed.

Algorithm

For each car i, compute arrival time: time[i] = (target - position[i]) / speed[i]
Pair each car as (position[i], time[i]) and sort by position in descending order
Initialize an empty stack
For each car in sorted order:
- If the stack is empty OR car's time > stack top: push car's time (new fleet)
- Otherwise: this car merges into the fleet at the stack top (skip)
Return the stack size (number of fleets)

Code

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        
        // Pair (position, arrival_time)
        vector<pair<int, double>> cars(n);
        for (int i = 0; i < n; i++) {
            cars[i] = {position[i], (double)(target - position[i]) / speed[i]};
        }
        
        // Sort by position descending
        sort(cars.begin(), cars.end(), [](auto& a, auto& b) {
            return a.first > b.first;
        });
        
        // Stack tracks fleet leader arrival times
        stack<double> st;
        
        for (auto& [pos, time] : cars) {
            // Only push if this car is slower than the fleet ahead
            if (st.empty() || time > st.top()) {
                st.push(time);
            }
        }
        
        return st.size();
    }
};

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        n = len(position)
        
        # Pair (position, arrival_time) and sort by position descending
        cars = sorted(
            [(position[i], (target - position[i]) / speed[i]) for i in range(n)],
            key=lambda x: -x[0]
        )
        
        # Stack tracks fleet leader arrival times
        stack = []
        
        for pos, time in cars:
            # Only push if this car is slower than the fleet ahead
            if not stack or time > stack[-1]:
                stack.append(time)
        
        return len(stack)

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        
        // Pair (position, arrival_time)
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i]) / speed[i];
        }
        
        // Sort by position descending
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
        
        // Stack tracks fleet leader arrival times
        Deque<Double> stack = new ArrayDeque<>();
        
        for (double[] car : cars) {
            // Only push if this car is slower than the fleet ahead
            if (stack.isEmpty() || car[1] > stack.peek()) {
                stack.push(car[1]);
            }
        }
        
        return stack.size();
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Computing arrival times is O(n). Sorting by position is O(n log n). The stack scan processes each car exactly once in O(n). The bottleneck is the sorting step, giving O(n log n) overall.

Space Complexity: O(n)

We store n (position, time) pairs. The stack can grow up to n entries in the worst case (all cars form separate fleets, e.g., when they are already sorted in decreasing order of arrival time). The sort may use O(log n) additional space.