# [Car Fleet](https://leetcode.com/problems/car-fleet/)
###### tags: `Leetcode`, `Medium`, `Stack`

## Approach

* Create a new list containing pairs of `(position, speed)` as elements in the list. Sort this list in descending order of position
* Initialize an empty stack
* For every tuple in this list, calculate the time taken to reach the destination using the formula

time = (target - position) / speed

* Add the time calculated above to the stack
* If the stack has more than one element then compare the time to the top value of the stack. If the time calculated now is less than or equal to the top value of the stack, then it means that eventually this car will catch up to the one ahead of it and will then move at the other car's pace. Hence, pop the value top element of the stack.
* Return the length of the stack

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(N)**

## Code

from typing import List


class CarFleet:
    def car_fleet(self, target: int, position: List[int], speed: List[int]) -> int:
        pairs = [(p, s) for p, s in zip(position, speed)]
        stack = []

        for p, s in sorted(pairs)[::-1]:
            time = (target - p) / s
            stack.append(time)
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()
        return len(stack)