NeetCode #357LC-853MediumStackNC 150NC 250
← Back to All Problems#357 · #853 · Car Fleet(车队)
📌 Problem Statement & Constraints
There are
n cars on a one-lane road heading to a target mile destination. position[i] and speed[i] describe car i. A faster car behind a slower one cannot pass, so it joins that car's fleet. A fleet is a group of cars at the same position and speed. Return the number of fleets that arrive at the target. Constraints: 1 <= n <= 10^5, 0 < target <= 10^6, all positions are distinct.💡 Core Algorithmic Approaches
- Sort the cars by position in descending order, so the closest car to the target is processed first.
- Compute each car's arrival time as
(target - position) / speed. - A car forms a new fleet if its arrival time is strictly greater than the fleet ahead of it; otherwise it catches up and joins.
- Track only the last fleet's time, since any car that joins a fleet is governed by that fleet's leader.
💻 Benchmark Python3 Implementation
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
cars = sorted(zip(position, speed), reverse=True) # closest first
fleets = 0
lead_d = lead_s = 0 # the fleet leader's (distance, speed)
for p, s in cars:
d = target - p
# new fleet if this car arrives strictly later than the leader
# compare d/s > lead_d/lead_s via cross multiplication (no floats)
if fleets == 0 or d * lead_s > lead_d * s:
fleets += 1
lead_d, lead_s = d, s
return fleets⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the scan is O(n).
💾 Space Complexity
O(n) for the sorted pairs (O(1) extra beyond that).
⚠️ Interview Pitfalls & Follow-ups
- Sorting ascending: the closest car must be processed first, so the order is descending by position.
- Using
>=in the comparison: an equal arrival time means the car catches the fleet and joins it, so the test is strictly greater. - Comparing floats:
(target - p) / scan produce precision issues; the cross-multiplied integer comparison is exact. - Thinking a faster car behind always forms its own fleet: it only does so if it arrives later than the fleet ahead.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.