⚡Flashcard Drill➔
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

  1. Sort the cars by position in descending order, so the closest car to the target is processed first.
  2. Compute each car's arrival time as (target - position) / speed.
  3. 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.
  4. 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) / s can 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems