853. Car Fleet LeetCode Solution

In this guide, you will get 853. Car Fleet LeetCode Solution with the best time and space complexity. The solution to Car Fleet problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Car Fleet solution in C++
Car Fleet solution in Java
Car Fleet solution in Python
Additional Resources

Problem Statement of Car Fleet

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.

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 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation:
There is only one car, hence there is only one fleet.
Example 3:

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

The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Constraints:

n == position.length == speed.length
1 <= n <= 105
0 < target <= 106
0 <= position[i] < target
All the values of position are unique.
0 < speed[i] <= 106

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

853. Car Fleet LeetCode Solution in C++

struct Car {
  int pos;
  double time;  // the time to reach the target
};

class Solution {
 public:
  int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int ans = 0;
    vector<Car> cars(position.size());

    for (int i = 0; i < position.size(); ++i)
      cars[i] = {position[i], (double)(target - position[i]) / speed[i]};

    ranges::sort(cars, ranges::greater{},
                 [](const Car& car) { return car.pos; });

    double maxTime = 0;  // the time of the slowest car to reach the target

    for (const Car& car : cars)
      // A car needs more time to reach the target, so it becomes the slowest.
      if (car.time > maxTime) {
        maxTime = car.time;
        ++ans;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

853. Car Fleet LeetCode Solution in Java

class Car {
  public int pos;
  public double time;

  public Car(int pos, double time) {
    this.pos = pos;
    this.time = time;
  }
}

class Solution {
  public int carFleet(int target, int[] position, int[] speed) {
    int ans = 0;
    Car[] cars = new Car[position.length];

    for (int i = 0; i < position.length; ++i)
      cars[i] = new Car(position[i], (double) (target - position[i]) / speed[i]);

    Arrays.sort(cars, (a, b) -> Integer.compare(b.pos, a.pos));

    double maxTime = 0; // the time of the slowest car to reach the target

    for (Car car : cars)
      // A car needs more time to reach the target, so it becomes the slowest.
      if (car.time > maxTime) {
        maxTime = car.time;
        ++ans;
      }

    return ans;
  }
}
// code provided by PROGIEZ

853. Car Fleet LeetCode Solution in Python

class Solution:
  def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
    ans = 0
    times = [
        float(target - p) / s for p, s in sorted(zip(position, speed),
                                                 reverse=True)]
    maxTime = 0  # the time of the slowest car to reach the target

    for time in times:
      # A car needs more time to reach the target, so it becomes the slowest.
      if time > maxTime:
        maxTime = time
        ans += 1

    return ans
 # code by PROGIEZ