853. Car Fleet

Problem Link

Each car moves toward the target at a constant speed. A faster car may catch up to a slower car ahead of it, but once they meet, they form a fleet and continue together at the slower speed.

If a car behind would reach the target earlier than or at the same time as the car ahead, it must catch up respective cars before the target and therefore becomes part of the same fleet. This turns the problem into comparing arrival times, not positions over time.

Since the car ahead controls the pace, we sort them by position in descending order, so we process cars closest to the target first. For each car, compute the time to reach the target: \(time = (target - position) / speed\). To track the arrival time for each fleet, we can use a stack where each element in the stack represents the arrival time of a fleet. When processing cars from closest to farthest:

• If the current car’s arrival time is less than or equal to the time at the top of the stack, it will catch up and merge with that fleet.
• Otherwise, it forms a new fleet and its time is pushed onto the stack.

This works because once cars are sorted by position, a car can only interact with the fleet immediately ahead of it.

Runtime Complexity

Time: \(O(nlogn)\), since we used sorting

Space: \(O(n)\), from stack

PythonGo

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        result = 0
        stk = []
        for dist, speed in sorted(zip(position, speed), reverse=True):
            stk.append((target-dist)/speed)
            if len(stk) >= 2 and stk[-1] <= stk[-2]:
                stk.pop()
        return len(stk)

type Car struct {
    pos   int
    speed int
}

func constructCars(position []int, speed []int) []Car {
    cars := make([]Car, len(position))
    for i := range position {
        cars[i] = Car{position[i], speed[i]}
    }

    sort.Slice(cars, func(i, j int) bool {
        return cars[i].pos > cars[j].pos // reverse=True
    })
    return cars
}

func carFleet(target int, position []int, speed []int) int {
    var stk []float64
    cars := constructCars(position, speed)
    var l int
    for _, car := range cars {
        stk = append(stk, float64(target-car.pos)/float64(car.speed))
        l = len(stk)
        if len(stk) >= 2 && stk[l-1] <= stk[l-2] {
            stk = stk[:l-1]
        }
    }
    return len(stk)
}

---