LeetCode Solution 853 - Car Fleet

Problem Statement

There are n cars going to the same destination along a one-lane road. The destination is at position target. Each car i has a starting position position[i] and a speed speed[i]. A car fleet is some non-empty set of cars that travel together at the same speed. If a car catches up to another car at the same position, they form a fleet, and the fleet's speed is determined by the slowest car in the fleet.

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

Example

Input:

 target = 12
 position = [10, 8, 0, 5, 3]
 speed = [2, 4, 1, 1, 3]

Output:

 3

---

Optimal Approach: Monotonic Stack

The most efficient way to solve this problem is by using a Monotonic Stack.

Algorithm Steps:

1. Sort the cars by their starting position in descending order.
2. Calculate the time taken for each car to reach the target.
3. Use a stack to track the fleets:
   • If a car reaches the destination later than the car in front, it forms a new fleet.
   • If a car reaches at the same time or earlier, it joins the existing fleet.

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<pair<int, double>> cars;
        
        for (int i = 0; i < n; i++) {
            cars.push_back({position[i], (double)(target - position[i]) / speed[i]});
        }
        
        sort(cars.rbegin(), cars.rend());
        stack<double> st;
        
        for (auto& car : cars) {
            double time = car.second;
            if (st.empty() || time > st.top()) {
                st.push(time);
            }
        }
        
        return st.size();
    }
};

---

Step-by-Step Explanation

1. Store position and time-to-destination as pairs.
2. Sort in descending order of position.
3. Use a stack to keep track of fleets.
4. If a car takes longer than the top of the stack, it forms a new fleet.

---

Dry Run with Sample Input

Given Input:

target = 12
position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]

Execution:

Car Position	Speed	Time to Target	Stack
10	2	1.0	[1.0]
8	4	1.0	[1.0]
5	1	7.0	[1.0, 7.0]
3	3	3.0	[1.0, 7.0, 3.0]
0	1	12.0	[1.0, 7.0, 3.0, 12.0]

Total Fleets: 3

---

Alternative Approaches

1. Brute Force (Simulating Car Movements)

• Time Complexity: O(N log N) (Sorting) + O(N) (Checking each pair) = O(N log N)
• Space Complexity: O(N)
• Why Not? Inefficient as it requires unnecessary tracking of individual movements.

2. Using HashMap

• Idea: Store each car’s arrival time and group them.
• Why Not? Sorting is required anyway, making it similar to the stack approach but more complex.

3. Dynamic Programming (DP)

• Idea: Use a DP array to store the earliest arrival time of a fleet.
• Why Not? Unnecessary extra space and computations compared to the stack.

---

Best Solution: Monotonic Stack

Approach	Time Complexity	Space Complexity	Efficiency
Brute Force	O(N²)	O(1)	❌ Slow
HashMap	O(N log N)	O(N)	❌ Complex
Dynamic Programming	O(N log N)	O(N)	❌ Extra Space
Monotonic Stack	O(N log N)	O(N)	✅ Best

The monotonic stack is the best approach since it efficiently tracks fleets while processing each element only once.

---

Conclusion

The Monotonic Stack approach provides an optimal O(N log N) solution for the Car Fleet problem. It efficiently determines the number of fleets arriving at the destination without unnecessary calculations.

Similar Problems for Practice:

1. Car Fleet II
2. Next Greater Element II
3. Trapping Rain Water

This problem is a great example of leveraging sorting and stacks to efficiently group related elements.