Leetcode 853

Problem Overview

The problem requires determining how many car fleets will arrive at a destination given the starting positions and speeds of the cars. A car fleet is a group of cars that travel together at the same speed due to the leading car.

Initial Analysis

Initially, I considered using a hash table to manage the positions and speeds of the cars. Here’s how I thought it might work:

  • Buckets for Positions: Using an unordered_map, each car’s position would be a key, and the speed would be the value.
  • Collision Detection: At each time tick, update the car positions. If two cars share a position, merge them into a fleet and adjust the speed.
  • Complexity Concerns: Continuously updating positions and merging fleets seemed computationally expensive, especially with large inputs.

While the hash table approach appeared promising due to its average O(1) complexity for insertions and lookups, the dynamic nature of updating positions and merging fleets introduced high overhead. This realization led me to explore more efficient solutions.

Transition to a Stack-Based Approach

Recognizing the potential inefficiencies of the hash table method, I shifted to a more straightforward and efficient stack-based approach. This method leverages sorting and a single pass through the list of cars to manage fleets.

Detailed Solution

  1. Calculate Time to Target: For each car, compute the time it will take to reach the target using:

    \[\text{time} = \frac{\text{target} - \text{position[i]}}{\text{speed[i]}}\]
  2. Sort Cars by Position: Sort the cars based on their starting positions in descending order. This allows us to process the farthest car first.

  3. Use a Stack to Track Fleets:

    • Initialize a stack to keep track of the maximum time of the current fleet to reach the target.
    • Iterate through the sorted list of cars:
      • If a car’s time to target is greater than the current maximum (top of the stack), it forms a new fleet.
      • If a car can catch up to the fleet in front, it joins that fleet.
//to be noticed, time is a real number not an integer
class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        assert(position.size() == speed.size() && "These 2 containers should be the same size.");
        if(position.size() == 1){return 1;}

        vector<float> time = vector<float>(position.size());
        for(size_t i = 0; i < time.size(); i++){
            time[i] = static_cast<float>(target - position[i]) / speed[i];
        }

        auto comparator = [&](int i, int j){
            return position[i] > position[j];
        };

        vector<int> indices(position.size());
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), comparator);

        vector<vector<float>> cars(2, vector<float>(position.size()));
        for(size_t i = 0; i < position.size() ; i++){
            cars[0][i] = static_cast<float>(position[indices[i]]);
            cars[1][i] = time[indices[i]];  
        }
  
        vector<float> stack{};
        stack.push_back(cars[1][0]);
        for(size_t i = 1; i < cars[1].size(); i++){
            if(cars[1][i] > stack.back()){
                stack.push_back(cars[1][i]);
            }
        }  

        return stack.size();
    }
};

Conclusion

This approach effectively reduces complexity by leveraging sorting and a stack to manage the fleets. The result is an efficient algorithm with a time complexity of $O(n log n)$ due to sorting and $O(n)$ for the single pass through the cars.

The process of transitioning from the hash table idea to the stack-based solution was a valuable learning experience. It underscored the importance of evaluating algorithm efficiency and adapting strategies to optimize performance.