Car Fleet
Detailed guide and Python implementation for the 'Car Fleet' problem.
1. Concept Overview
The 'Car Fleet' problem is a key challenge in the Stack section.
This implementation focuses on easy-level logic in Python.
We prioritize technical accuracy and code readability in our provided solutions.
2. Real-World Applications
3. Visual Intuition
Visualizing the logic flow for Car Fleet.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Read the problem statement for Car Fleet carefully.
2. Formulate brute force
Draft a simple iterative solution.
3. Identify inefficiency
Look for redundant calculations.
4. Optimize search path
Use hashing or sorting to speed up the process.
5. Final Implementation
Clean up the code for production standards.
Problem Statement
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
You are given two integer arrays position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car's speed. The distance between these two cars is ignored (they are assumed to be at the same position).
A car fleet is some non-empty set of cars driving at the same position and same speed. A single car is also a car fleet.
Return the number of car fleets that will arrive at the destination.
Write a function carFleet(target: int, position: List[int], speed: List[int]) -> int.
- •n == len(position) == len(speed)
- •1 <= n <= 10^5
- •0 < target <= 10^6
- •0 <= position[i] < target
- •0 < speed[i] <= 10^6
- •All positions are unique
Examples
target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
3
Cars at positions 10 and 8: car at 8 catches car at 10 (both arrive at time 1), forming 1 fleet. Car at 0: arrives at time 12. Car at 5: arrives at time 7. Car at 3: arrives at time 3, catches car at 5 at time 7, but car at 5 arrives at 7 too. Cars at 3 and 5 form a fleet. Total: 3 fleets.
target = 10, position = [3], speed = [3]
1
Only one car, so one fleet.
target = 100, position = [0, 2, 4], speed = [4, 2, 1]
1
All cars eventually form a single fleet.
Need a Hint?
Edge Cases to Watch
- Empty input structures
- Single element inputs
- Large numerical bounds
Ready to Solve?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Interview Insights & Variations
Complexity Analysis Breakdown
Why Time: Directly evaluates all possibilities.
Why Space: Uses standard local memory.
Why Time: Optimized paths reduce total operations.
Why Space: May trade memory for speed.
Optimized Solution Python Code
Optimized Solution Python Code
def car_fleet_opt(target, position, speed):
pair = [[p, s] for p, s in zip(position, speed)]
stack = []
for p, s in sorted(pair)[::-1]:
stack.append((target - p) / s)
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)Brute Force Code (Spoiler Guarded)
Brute Force Code (Spoiler Guarded)
def car_fleet_brute(target, position, speed):
cars = sorted(zip(position, speed), reverse=True)
times = [(target - p) / s for p, s in cars]
fleets = 0
curr_max_time = 0
for t in times:
if t > curr_max_time:
fleets += 1
curr_max_time = t
return fleetsAlgorithm Pattern Checklist
When dealing with Stack data patterns.
Core Prerequisites
Revision Key Notes
Common Mistakes & Pitfalls
Related Questions
Recommended Python Resources
Expand your knowledge with related interactive tutorials, cheat sheets, and code comparisons.
Python Loops
Learn how to use Python loops to iterate over data. Master for loops, while loops, break, continue, and loop best practices with interactive examples.
How to Sort a List in Python
Learn how to sort a list in Python using the sort() method and the sorted() function. Discover custom key sorting and reverse order examples.
Python String Methods
A complete reference guide for Python string manipulation. Master formatting, searching, splitting, replacing, and checking string properties.
Python vs JavaScript: Which Programming Language is Best?
A comprehensive comparison between Python and JavaScript. Explore syntax differences, performance, use cases (backend vs frontend), and coding examples.