Car Fleet medium

Problem Statement

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

Each car starts at a position position[i] miles from the starting point, and has a speed speed[i] miles per hour.

A car can only be overtaken by another car if its speed is strictly less than the other car's speed.

A car fleet is defined as a group of cars that are moving together such that the last car in the fleet has a speed no lower than the speed of the car directly ahead of it.

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

Example 1

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] Output: 3 Explanation: The cars starting at 10 and 8 are moving at 2 and 4 mph respectively. Since 4 > 2, the car at 10 will eventually be overtaken by the car at 8. The car at 8 will not be overtaken, so we have one fleet. The cars at 5 and 3 will be overtaken by the car at 8, as well as by the car at 10. The cars at 0 will also be overtaken by the cars at 8 and 10 and 5 and 3, so we have another fleet. Hence, there are 3 fleets in total.

Example 2

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

Steps

1. Sort: Sort the cars by their position in ascending order. This ensures we process cars from closest to furthest from the target.

2. Calculate Arrival Times: For each car, calculate the time it takes to reach the target: (target - position[i]) / speed[i].

3. Iterate and Merge Fleets: Iterate through the sorted cars from the last car to the first. Maintain a stack to track the arrival times of the fleets. If the current car's arrival time is greater than or equal to the top of the stack (meaning it will not be overtaken), push its arrival time onto the stack. Otherwise, the current car merges with the existing fleet, and we don't need to add its arrival time.

4. Return Fleet Count: The size of the stack after processing all cars represents the number of car fleets.

Explanation

The core idea is to process cars in reverse order of their positions. This allows us to efficiently determine whether a car will be overtaken. If a slower car is behind a faster car, it will inevitably be overtaken. We use a stack to keep track of the arrival times of the fleets. If a car's arrival time is greater than or equal to the arrival time of the last fleet, it forms a new fleet. Otherwise, it joins the existing fleet.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        if (n == 0) return 0;

        // Create a list of car information (position, speed, arrival time)
        List<(int pos, int spd, double arrival)> cars = new List<(int, int, double)>();
        for (int i = 0; i < n; i++) {
            cars.Add((position[i], speed[i], (double)(target - position[i]) / speed[i]));
        }

        // Sort cars by position in ascending order
        cars.Sort((a, b) => a.pos.CompareTo(b.pos));

        // Use a stack to track fleet arrival times
        Stack<double> stack = new Stack<double>();
        stack.Push(cars[n - 1].arrival); // Add the last car's arrival time to the stack

        // Iterate through cars from last to first
        for (int i = n - 2; i >= 0; i--) {
            if (cars[i].arrival >= stack.Peek()) { // If arrival time is greater than or equal to the top of the stack, it's a new fleet
                stack.Push(cars[i].arrival);
            }
        }

        // The number of fleets is the size of the stack
        return stack.Count;
    }
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(N) in the worst case, due to the stack and the list used to store car information. In practice, the space used by the list might be considered part of the input space.