Car Fleet

Problem Description

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target. You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour. A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car. A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet. If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet. Return the number of car fleets that will arrive at the destination.

Key Insights

• Cars that start farther back can catch up to those ahead if their speed is sufficient.
• The number of fleets is determined by how many groups of cars can reach the target together without being overtaken.
• Sorting cars based on their position helps in determining which cars will form fleets.
• We can calculate the time it takes each car to reach the target and use that to determine the formation of fleets.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the cars by their position.
Space Complexity: O(n) - for storing time to reach the target.

Solution

To solve the problem, we can follow these steps:

1. Pair each car's position with its speed and calculate the time it takes to reach the target.
2. Sort the cars based on their starting position.
3. Traverse the sorted list from the back to the front, merging fleets when a car can catch up to the fleet ahead of it.
4. Count how many distinct fleets are formed.

We will use an array to store the time each car takes to reach the target, and a counter for the number of fleets.

Code Solutions