853. Car Fleet

📝 Problem Details

• Title: 853. Car Fleet
• Link: https://leetcode.com/problems/car-fleet/
• Difficulty: Medium
• Tags/Categories: Stack Monotonic-Stack Sorting

💭What Were My Initial Thoughts?

- we will need to store the position and speed values in a vector of pairs to ensure they are coupled
- sorting the paired elements by their starting positions 
- start from the back of the array first (the last position)
	- calculate the time it takes a car at position i to get to target
	- compare that value to the next value 
	- if the next value has a shorter time , remove that value from the stack as its now apart from the fleet in front of it 
	- return the size of the stack 

🤔What Did I Struggle With?

~

💡 Explanation of Solution

same as intuition 

⌛ Complexity Analysis

Time Complexity: O(n log n)
	- traversal through the stack and initial lists are linear in time
	- however, we need to sort the cars by starting position which is O(n log n)

Space Complexity: O(n) for use of stack to store elements

💻 Implementation of Solution

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<pair<int, double>> cars(n);
 
        // store the position and the time it takes to reach the finish (target)
        for(int i=0; i < n; i++) {
            cars[i] = {position[i], (double)(target - position[i]) / speed[i]};
        }
 
        // sort cars by starting position
        sort(cars.begin(), cars.end());
        stack<double> stk;
 
        // iterate from the end of the cars array to collect fleets
        for(int i = n-1; i >= 0; i--) {
            // If the current car's time is greater than the time of the last fleet on the stack,
            // it means this car will form a new fleet.
            if (stk.empty() || cars[i].second > stk.top()) {
                stk.push(cars[i].second);
            }
        }
 
        return stk.size();
    }
};