Algorithm Notes
Summary: Car Fleet — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.
Big-O Guide
Source
"""
Car Fleet
There are `n` cars going to the same destination along a one-lane road.
The destination is `target` miles away. Each car `i` has a position and speed.
A car fleet forms when one catches up to another before the target.
Return how many car fleets will arrive at the destination.
"""
from interview_workbook.leetcode._registry import register_problem
from interview_workbook.leetcode._types import Category, Difficulty
class Solution:
def solve(self, target, position, speed) -> int:
"""Return the number of car fleets that will arrive at the target."""
cars = sorted(zip(position, speed), reverse=True)
stack = []
for pos, spd in cars:
time = (target - pos) / spd
if not stack or time > stack[-1]:
stack.append(time)
return len(stack)
def demo() -> str:
target = 12
position = [10, 8, 0, 5, 3]
speed = [2, 4, 1, 1, 3]
print(f"Target: {target}, Positions: {position}, Speeds: {speed}")
s = Solution()
result = s.solve(target, position, speed)
print(f"Final result: {result}")
return f"Car Fleet to target {target} with positions {position} and speeds {speed} -> {result}"
if __name__ == "__main__":
demo()
register_problem(
id=853,
slug="car_fleet",
title="Car Fleet",
category=Category.STACK,
difficulty=Difficulty.MEDIUM,
tags=["stack", "greedy", "sorting"],
url="https://leetcode.com/problems/car-fleet/",
notes="Sort cars by position and collapse fleets using a stack.",
)