Problem statement

https://leetcode.com/problems/car-fleet/

Solution

First, we need to sort our cars by positions, starting from big ones and going to small ones. Let lead be time needed for the first car in fleet to reach destination. We iterate over cars and if we see that arriving time for car is more than lead, it means that this car will never gain leading car and we need to create new fleet. In opposite case, that is arriving time for care is less than lead we do nothing: leading car is still the same.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

class Solution:
    def carFleet(self, target, position, speed):
        cars = sorted(zip(position, speed), key = lambda x: -x[0])
        lead, ans = 0, 0
        
        for p, s in cars:
            if (target - p)/s > lead :
                lead = (target - p)/s
                ans += 1
                
        return ans