Car Fleet

StackArraySorting

25 min

Problem Statement

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

You are given two integer arrays position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

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

Example

Example 1:

Target: 12

Positions:

Speeds:

Result (Number of Fleets):

Solution

The key insight is to process cars from closest to the target to furthest. If a car behind would arrive sooner than the car ahead of it, it will catch up and form a fleet. We can use a stack to track the arrival times of the fleets.

Algorithm Steps

Create pairs of (position, speed) for each car.
Sort these pairs in descending order of position.
Initialize an empty stack to store arrival times.
Iterate through the sorted cars:
- Calculate the time it takes for the current car to reach the target.
- If the stack is empty or the current car's arrival time is greater than the arrival time of the last fleet on the stack, it forms a new fleet. Push its arrival time onto the stack.
The size of the stack is the number of car fleets.

Cars (Sorted by Position)

Pos: 10, Spd: 2, Time: N/A

Pos: 8, Spd: 4, Time: N/A

Pos: 5, Spd: 1, Time: N/A

Pos: 3, Spd: 3, Time: N/A

Pos: 0, Spd: 1, Time: N/A

Fleet Arrival Times (Stack)

Start. Cars sorted by position.

Car Fleet Solution


class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        pair = sorted(zip(position, speed), reverse=True)
        stack = []
        for p, s in pair:
            time = (target - p) / s
            if not stack or time > stack[-1]:
                stack.append(time)
        return len(stack)