Car Fleet

Mediumarraystacksortingmonotonic-stack
Category: Stack
Companies that ask this question:
AmazonGoogleFacebook
LeetCode →NeetCode →

Approach

Car Fleet

Problem

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. A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

Example 1:

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

Explanation:
- Car at position 10 with speed 2: time = (12-10)/2 = 1.0
- Car at position 8 with speed 4: time = (12-8)/4 = 1.0
- Car at position 0 with speed 1: time = (12-0)/1 = 12.0
- Car at position 5 with speed 1: time = (12-5)/1 = 7.0
- Car at position 3 with speed 3: time = (12-3)/3 = 3.0

Sort by position (descending): [10,8,5,3,0]
Times: [1.0, 1.0, 7.0, 3.0, 12.0]
- Fleet 1: Cars at pos 10 and 8 (both arrive at time 1.0)
- Fleet 2: Cars at pos 5 and 3 (car at 3 catches up)
- Fleet 3: Car at pos 0

Answer: 3 fleets

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1

Example 3:

Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1

Approach: Sort + Stack (Optimal)

Intuition

Key insights:

  1. Sort by position (descending): Process cars from closest to target to farthest
  2. Calculate time to reach target for each car: time = (target - position) / speed
  3. Use monotonic stack: If a car behind takes longer time, it forms a new fleet

Why This Works

  • Cars ahead (closer to target) can't be caught by cars behind them if they take less time
  • If a car behind takes more time, it will never catch up → new fleet
  • If a car behind takes less time, it will catch up and join the fleet ahead

Algorithm

def carFleet(target, position, speed):
    # Pair position and speed, sort by position descending
    cars = sorted(zip(position, speed), reverse=True)
    
    stack = []
    for pos, spd in cars:
        time = (target - pos) / spd
        
        # If this car takes more time, it's a new fleet
        if not stack or time > stack[-1]:
            stack.append(time)
        # Otherwise, it catches up to the fleet ahead
    
    return len(stack)

Example Walkthrough

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

  1. Sort by position: [(10,2), (8,4), (5,1), (3,3), (0,1)]
  2. Calculate times: [1.0, 1.0, 7.0, 3.0, 12.0]
  3. Process:
    • pos=10: time=1.0, stack=[1.0] (fleet 1)
    • pos=8: time=1.0 ≤ 1.0, joins fleet → stack=[1.0]
    • pos=5: time=7.0 > 1.0, new fleet → stack=[1.0, 7.0]
    • pos=3: time=3.0 ≤ 7.0, joins fleet → stack=[1.0, 7.0]
    • pos=0: time=12.0 > 7.0, new fleet → stack=[1.0, 7.0, 12.0]
  4. Answer: 3 fleets

Time Complexity

  • O(n log n): Sorting dominates

Space Complexity

  • O(n): Stack storage

Alternative Approach: Without Stack

Simply count how many times we see an increasing time value.

def carFleet(target, position, speed):
    cars = sorted(zip(position, speed), reverse=True)
    fleets = 0
    prev_time = 0
    
    for pos, spd in cars:
        time = (target - pos) / spd
        if time > prev_time:
            fleets += 1
            prev_time = time
    
    return fleets

Same complexity, slightly more space-efficient.

Solution

java
1/**
2 * Car Fleet
3 * Time: O(n log n) due to sorting
4 * Space: O(n)
5 */
6
7import java.util.*;
8
9// Approach 1: Sort + Stack (Optimal)
10class Solution {
11    public int carFleet(int target, int[] position, int[] speed) {
12        int n = position.length;
13        
14        // Create array of (position, time) pairs
15        double[][] cars = new double[n][2];
16        for (int i = 0; i < n; i++) {
17            cars[i][0] = position[i];
18            cars[i][1] = (double)(target - position[i]) / speed[i];
19        }
20        
21        // Sort by position descending
22        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
23        
24        Deque<Double> stack = new ArrayDeque<>();
25        for (double[] car : cars) {
26            double time = car[1];
27            
28            // If this car takes more time, it's a new fleet
29            if (stack.isEmpty() || time > stack.peek()) {
30                stack.push(time);
31            }
32        }
33        
34        return stack.size();
35    }
36}
37
38// Approach 2: Without Stack (More space-efficient)
39class Solution2 {
40    public int carFleet(int target, int[] position, int[] speed) {
41        int n = position.length;
42        
43        double[][] cars = new double[n][2];
44        for (int i = 0; i < n; i++) {
45            cars[i][0] = position[i];
46            cars[i][1] = (double)(target - position[i]) / speed[i];
47        }
48        
49        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
50        
51        int fleets = 0;
52        double prevTime = 0;
53        
54        for (double[] car : cars) {
55            double time = car[1];
56            if (time > prevTime) {
57                fleets++;
58                prevTime = time;
59            }
60        }
61        
62        return fleets;
63    }
64}
65
66// Approach 3: Using TreeMap for sorting
67class Solution3 {
68    public int carFleet(int target, int[] position, int[] speed) {
69        TreeMap<Integer, Double> map = new TreeMap<>(Collections.reverseOrder());
70        
71        for (int i = 0; i < position.length; i++) {
72            map.put(position[i], (double)(target - position[i]) / speed[i]);
73        }
74        
75        int fleets = 0;
76        double prevTime = 0;
77        
78        for (double time : map.values()) {
79            if (time > prevTime) {
80                fleets++;
81                prevTime = time;
82            }
83        }
84        
85        return fleets;
86    }
87}
88
Loading visualizer...