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.

You are given two integer arrays position and speed, both of length n, where position[i] is the position of the i-th car and speed[i] is the speed of the i-th car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it, forming a car fleet. A car fleet is some non-empty set of cars driving at the same speed. Note that no other cars can join a fleet once it is formed.

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

Clarifying Questions

  1. Are there any constraints on the values of position and speed?
    • Yes, according to typical problem constraints:
      • 1 <= n <= 10^5
      • 0 <= position[i] < target <= 10^6
      • 0 <= speed[i] <= 10^6
  2. What should be done if two cars are at the same position but have different speeds?
    • They will be treated as separate entities initially, but one might catch up with the other to form a fleet.
  3. Does the order of cars matter in the input arrays?
    • No, the order of the cars in the position and speed arrays does not matter.
  4. What is the output if all cars are at the same position and have the same speed?
    • They would form a single fleet since they are driving at the same speed.

Strategy

  1. Calculate the Time to Reach the Destination:
    • For each car, calculate the time it takes to reach the destination using: [ \text{time}[i] = \frac{\text{target} - \text{position}[i]}{\text{speed}[i]} ]
  2. Sort the Cars by Starting Position:
    • Sort the cars by their position in descending order, so we can process them from the car closest to the destination to the farthest.
  3. Simulate the Formation of Fleets:
    • Iterate through the sorted list, and use a stack (or just a variable) to keep track of the time it takes for the last fleet to reach the destination.
    • If a car takes more time than the last recorded fleet time, it starts a new fleet.

Code

#include <vector>
#include <algorithm>

int carFleet(int target, std::vector<int>& position, std::vector<int>& speed) {
    int n = position.size();
    std::vector<std::pair<int, double>> cars(n);

    // Step 1: Calculate the time for each car to reach the target
    for (int i = 0; i < n; ++i) {
        double time = static_cast<double>(target - position[i]) / speed[i];
        cars[i] = {position[i], time};
    }

    // Step 2: Sort cars by starting position in descending order
    std::sort(cars.begin(), cars.end(), [](const auto& a, const auto& b) {
        return a.first > b.first;
    });

    // Step 3: Count the number of fleets
    int fleets = 0;
    double last_time = 0.0;
    for (const auto& car : cars) {
        double current_time = car.second;
        if (current_time > last_time) {
            // Current car forms a new fleet
            fleets++;
            last_time = current_time;
        }
    }

    return fleets;
}

Time Complexity

Overall, the time complexity of the solution is (O(n \log n)) due to the sorting step.

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