algoadvance

Leetcode 853. Car Fleet

Problem Statement

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

Each car i has a constant speed speed[i] (in miles per hour), and initially present at position position[i] miles towards the target.

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 if the cars meet.

The number of car fleets is the total number of groups of cars that are traveling at the same speed.

Given target, an integer, and two integer arrays position and speed, both of length n, return the number of car fleets.

Example

• Example 1:
  • Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
  • Output: 3
  • Explanation: ```
    • The cars starting at positions 10 and 8 have speeds of [2, 4] respectively. They will meet at position 12 in 1 and 1 hour respectively forming a fleet.
    • The car starting at position 0 will reach in position 12 in 12 hours.
    • The car starting at position 5 will reach in position 12 in 7 hours.
    • The car starting at position 3 will reach in position 12 in 5 hours. Therefore, there are 3 car fleets ```

Clarifying Questions

1. Will there always be at least one car?
   • Yes, the problem guarantees that n >= 1.
2. Are the positions and speeds guaranteed to be positive integers?
   • Yes, all values in the position and speed arrays are positive integers.
3. Can two cars have the same position?
   • No, all cars have distinct start positions.

Strategy

1. Calculate Time to Target: Determine the amount of time each car will take to reach the target by using the formula:

   time = (target - position[i]) / speed[i]
   

2. Sort by Position: Sort the cars by their starting position. This way, we can deal with cars from the closest to the furthest from the target.
3. Manage Fleets: Iterate over the sorted list of cars and use a stack to manage the fleets:
   • Start by pushing the time required for the first car.
   • For each subsequent car, check if it can catch the car in the fleet in front of it.
   • If it can’t catch the car in front, this car forms a new fleet.
4. Count Fleets: The size of the stack at the end will give the number of car fleets.

Code

import java.util.Arrays;

public class CarFleet {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        if (n == 0) {
            return 0;
        }
        
        // Create an array of cars with their position and time to reach the target
        double[][] cars = new double[n][2];
        for (int i = 0; i < n; ++i) {
            cars[i][0] = position[i];
            cars[i][1] = (double) (target - position[i]) / speed[i];
        }
        
        // Sort cars by their starting position
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));
        
        int fleets = 1;
        double curTime = cars[n - 1][1];
        
        for (int i = n - 2; i >= 0; --i) {
            if (cars[i][1] > curTime) {
                fleets++;
                curTime = cars[i][1];
            }
        }
        
        return fleets;
    }
}

Time Complexity

• Sorting the array: O(n log n), where n is the number of cars.
• Single pass to calculate the number of fleets: O(n).

Overall, the time complexity is O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?