Introduction

The Car Fleet problem involves determining how many groups of cars reach the destination.

Rules:

Cars moving at same speed after collision form one fleet.

A faster car:

  • cannot pass a slower car ahead
  • joins the same fleet

The task is to:

  • count total car fleets reaching target

Example:

Input:
target = 12
position = [10,8,0,5,3]
speed = [2,4,1,1,3]

Output:
3

Explanation:

Cars combine into 3 fleets before reaching target.

This problem is one of the most important applications of:

Stack + Sorting Technique

Constraints

1 <= n <= 10^50 < target <= 10^6
0 <= position[i] < target
1 <= speed[i] <= 10^6

Approach 1 : Brute Force (Simulation)

Explanations:

Explanation:

The idea is:

  • simulate movement of every car
  • compare collisions manually
  • merge fleets repeatedly

Steps:

  1. Move all cars.
  2. Detect collisions.
  3. Merge fleets.
  4. Repeat simulation.

This approach becomes inefficient because:

  • repeated simulation
  • floating-point calculations
  • large time complexity

So stack-based solution is preferred.

Dry Run

Input:target = 12
position = [10,8,0,5,3]
speed = [2,4,1,1,3]

Arrival Times:
10 -> 1
8  -> 1
5  -> 7
3  -> 3
0  -> 12

Fleets:
(10,8) -> one fleet
(5) -> one fleet
(3,0) -> one fleet

Final Output:
3

Practice :

Complexity Analysis :

Time Complexity:- O(n log n)Explanation :
Sorting dominates time complexity.

Space Complexity:- O(n)
Explanation :
Extra storage is used for car information.

Approach 2 : Optimal Solution(Using Monotonic Stack)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • sort cars by position
  • calculate arrival time
  • maintain fleets using stack

Rules:

  • smaller arrival time joins previous fleet
  • larger arrival time forms new fleet

This efficiently counts fleets.

Dry Run

Input:target = 12
position = [10,8,0,5,3]
speed = [2,4,1,1,3]

Step 1:
Arrival times:
1,1,12,7,3

Step 2:
Traverse from right
12 -> new fleet
7 -> new fleet
3 -> joins fleet
1 -> new fleet
1 -> joins fleet

Final Output:
3

Practice :

Complexity Analysis :

Time Complexity:- O(n log n)Explanation :
Sorting cars dominates time complexity.

Space Complexity:- O(n)
Explanation :
Stack stores fleet arrival times.

Why This Problem is Important

This problem builds the foundation for:

  • Monotonic stack
  • Greedy algorithms
  • Sorting techniques
  • Collision simulation
  • Fleet merging logic

Real-World Applications

Car Fleet concepts are used in:

  • Traffic simulations
  • Fleet management systems
  • Vehicle tracking systems
  • Road network analysis
  • Autonomous driving systems

Common Beginner Mistakes

  • Incorrect sorting order
  • Wrong fleet merge condition
  • Incorrect arrival time calculation
  • Traversing in wrong direction
  • Ignoring equal arrival times

Interview Tip

Interviewers often expect:

  • sorting optimization
  • monotonic stack usage
  • fleet merge explanation
  • O(n log n) solution

Always explain:

  • why cars are processed from right to left
  • how arrival times determine fleet formation

Related Questions

  • Asteroid Collision
  • Daily Temperatures
  • Next Greater Element
  • Largest Rectangle in Histogram
  • Monotonic Stack Problems

Final Takeaway

The Car Fleet problem is one of the most important monotonic stack + greedy problems.

It teaches:

  • fleet merging
  • sorting traversal
  • monotonic stack logic
  • arrival time processing

Understanding this problem builds a strong foundation for:

  • greedy algorithms
  • advanced stack concepts
  • interview-level simulation problems.