Car Fleet

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• If a car catches up with a different car, it will slow down.
• Therefore, this hints to us that we should sort in descending order of position.
• This is because:
  • A car can be at most the speed of the car in front of it.
  • That is because the car must slow down to the speed of the car in front of it if it indeed catches up (proof by contradiction).
• So, the problem thereby reduces to:
  • Keep track of the current car fleet, and repeatedly check previous cars to see if they catch up to the current car.
  • If they do, then keep checking against the car with the greatest position.
  • Otherwise, note that you have another car fleet and reset the car fleet to the car that couldn’t form one.
• In this sense, the problem lends itself well to using a Stack.

Complexity

Runtime

$O(NlogN)$ due to sorting

Space

$O(N)$ for keeping the stack.

Code

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        y = target
        car_stack = sorted(zip(position, speed))
        fleets = 1
        b, m = car_stack.pop()
        cur_top_iterations = (y - b) / m
 
        while car_stack:
            b, m = car_stack.pop()
            iterations = (y - b) / m
            if iterations > cur_top_iterations:
                cur_top_iterations = iterations
                fleets += 1
 
        return fleets

Notes

Cards

START Basic Front: Car Fleet Back: Sort in descending order of position, checking if the car before it the car with greatest position catches up with it.

END

---

References

• Car Fleet