Car Fleet Problem Solution | Java Implementation for Traffic Flow Analysis

The Car Fleet problem involves determining how many car fleets form when cars travel toward a target destination, considering their speeds and positions. This solution uses a stack-based approach to efficiently group cars into fleets based on arrival times.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Are the cars guaranteed to have distinct positions initially, or can multiple cars start at the same position?
2. What is the expected time complexity for the solution? Should we aim for O(n log n) or better?
3. Can we modify the input array, or do we need to preserve the original order?
4. How should we handle cases where there are no cars or just one car?
5. Should we return the number of fleets or the actual fleets themselves?

Restatement in my own words: We have a number of cars positioned on a single-lane road approaching a target destination. Each car has a starting position and a maximum speed. Cars cannot overtake each other, so if a faster car catches up to a slower one ahead, they form a "fleet" and move together at the slower car's speed. We need to determine how many distinct fleets will arrive at the target.

Problem constraints and assumptions:

• All cars are moving in the same direction (toward target)
• Cars cannot overtake each other, so they form groups based on relative speeds and positions
• Each car has a specific starting position and maximum speed
• The target is at a fixed distance ahead of all cars
• We're counting the number of distinct fleets that reach the target

Key data shape and structure:

• Input consists of arrays or lists of car positions and speeds
• Each car can be represented as a pair (position, speed)
• The problem has a natural ordering based on car position from the target
• The solution requires considering cars in reverse order of their starting positions

Core insight: Cars that are closer to the target and faster than cars ahead of them will eventually form fleets with those ahead, so we need to process cars from the target direction and track when new fleets form.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern here is sorting + monotonic stack/queue. This is a classic "car fleet" problem that requires analyzing cars moving in the same direction with different speeds and positions to determine how many fleets form.

Wording that signals the pattern

• "Cars are moving in the same direction" - indicates we're dealing with a sequential problem where order matters
• "Speeds and positions vary" - suggests we need to compare relative positions and speeds to determine interactions
• "Fleet formation" - implies grouping based on some criteria (cars that can't overtake each other form one group)
• "Target position" - gives us a clear endpoint to calculate arrival times

Why this problem fits that pattern

This is fundamentally about determining when cars will form groups based on their relative positions and speeds. The key insight is that cars cannot overtake each other, so if a car behind is faster than one in front, it will eventually catch up and form a fleet with the slower car ahead.

The core pattern is that we need to:

1. Sort cars by their starting positions (or arrival times)
2. Process them in order to determine which ones form fleets
3. Use a monotonic property (faster cars can only form fleets with slower ones ahead)

Core insight needed to solve it

The critical insight is that we can think of this as a monotonic decreasing problem: if we process cars from the one closest to target backwards, we only need to track the "slowest" fleet speed at each position. Any car that arrives at or before the time of the current slowest fleet will join it, otherwise it forms a new fleet.

This is because cars cannot overtake, so once we know the slowest car in a group, any faster car that reaches the target at or before that time will merge into the same fleet.

The mathematical insight is: if car A arrives at time T₁ and car B arrives at time T₂ where T₂ ≤ T₁, then B will eventually catch up to A and form the same fleet.

3. Approach Evolution

My first instinct is to think about this as a simulation problem where I need to track when cars reach the target, but that would be O(n²) because for each car I'd have to simulate all the cars ahead of it. Let me think about how to optimize this.

The key insight is that cars can only move at the speed of the slowest car in front of them, so if a car is faster than the one in front, it will eventually catch up and form a fleet with that car. This means I don't need to simulate every car's movement - I just need to determine which cars form fleets together.

I notice that if I sort the cars by their position in descending order (closest to target first), then I can process them sequentially. When a car is faster than the one ahead of it, it will join that fleet. But more importantly, I can calculate when each car reaches the target and compare those times to determine fleet formation.

Let me think about this more carefully - if I process cars from the closest to target to farthest, and calculate when each car reaches the target, then a car that reaches the target at or before the car ahead of it will form a fleet with that car. This is because it will never overtake the car ahead of it.

So my approach will be:

1. Sort cars by position in descending order (closest to target first)
2. For each car, calculate when it reaches the target
3. If that time is less than or equal to the previous car's arrival time, they form a fleet
4. Otherwise, it creates a new fleet

This is O(n log n) due to sorting, but the processing afterward is O(n), which is much better than the brute force O(n²) approach.

The key invariant I'm maintaining is that when processing cars in order from closest to target to farthest, if a car arrives at or before the previous car's arrival time, they're in the same fleet.

// My approach is to sort cars by position and process them from closest to target
// This way, I can determine fleet formation by comparing arrival times
// Cars that arrive at or before the previous car's time form the same fleet
// Time complexity: O(n log n) due to sorting, O(n) for processing
// Space complexity: O(n) for storing the cars and their arrival times

4. Data Structure Choice

For the Car Fleet problem, I'll use a combination of data structures to efficiently solve the problem:

Primary Data Structures

1. Array/List of Car Objects - To store car positions and speeds

   • Why needed: We need to process each car's position and speed information
   • Time impact: O(n) for initialization, O(1) for access
   • Space impact: O(n) to store all car data

2. Priority Queue/Sorted Array - To process cars from rightmost to leftmost position

   • Why needed: Cars are processed in order of their positions (right to left) to determine fleet formation
   • Time impact: O(n log n) for sorting, O(1) for access to next car
   • Space impact: O(n) for the sorted structure

Implementation Strategy

I'll use a Car class to encapsulate position and speed data, then sort cars by position in descending order. This allows us to process cars from rightmost to left, which is crucial for determining fleet formation.

class Car {
    int position;
    int speed;
    
    Car(int position, int speed) {
        this.position = position;
        this.speed = speed;
    }
}

The key insight is that we process cars from right to left because:

• Cars to the right cannot be overtaken by cars behind them
• When we process from rightmost to left, we can easily determine if a car will form a new fleet or join an existing one
• This approach avoids complex collision detection logic

The sorting operation is essential and requires O(n log n) time, but this is unavoidable since we need to process cars in position order. The space complexity remains O(n) for storing the car data.

Helper Structures

I'll use a simple ArrayList to store car objects and Java's built-in Collections.sort() method for sorting, which provides clean and efficient implementation without requiring custom comparator logic.

This choice is optimal because:

• It's simple to implement and understand
• Java's sorting is highly optimized (Timsort)
• It naturally handles the right-to-left processing requirement
• No custom data structure overhead or complexity

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

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

First, I'll sort cars by position in descending order:

• Car 1: position=10, speed=2
• Car 2: position=8, speed=1
• Car 3: position=5, speed=1
• Car 4: position=3, speed=3
• Car 5: position=0, speed=1

Now I'll process each car from the front (closest to target):

Step 1: Car at position 10, speed 2

• Time to reach target = (12-10)/2 = 1 hour
• Fleet time = 1.0 hours
• Since this is the first car, it forms a new fleet: fleet count = 1

Step 2: Car at position 8, speed 4

• Time to reach target = (12-8)/4 = 1 hour
• Fleet time = 1.0 hours
• This car takes same time as previous fleet leader, so it joins the same fleet: fleet count = 1

Step 3: Car at position 5, speed 1

• Time to reach target = (12-5)/1 = 7 hours
• Fleet time = 7.0 hours
• This car takes longer than previous fleet leader (1.0 hours), so it forms a new fleet: fleet count = 2

Step 4: Car at position 3, speed 3

• Time to reach target = (12-3)/3 = 3 hours
• Fleet time = 3.0 hours
• This car takes less time than previous fleet leader (7.0 hours), so it joins the existing fleet: fleet count = 2

Step 5: Car at position 0, speed 1

• Time to reach target = (12-0)/1 = 12 hours
• Fleet time = 12.0 hours
• This car takes longer than previous fleet leader (3.0 hours), so it forms a new fleet: fleet count = 3

Final result: 3 fleets

The key insight is that we process cars from closest to farthest from target, and whenever a car takes longer than the current fleet leader's time, it must form its own fleet since it cannot catch up.

public int carFleet(int target, int[] position, int[] speed) {
    int n = position.length;
    
    // Create array of car data and sort by position in descending order
    int[][] cars = new int[n][2];
    for (int i = 0; i < n; i++) {
        cars[i][0] = position[i];
        cars[i][1] = speed[i];
    }
    
    // Sort by position in descending order
    Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0]));
    
    int fleets = 0;
    double lastFleetTime = -1.0; // Time of the fleet leader
    
    for (int i = 0; i < n; i++) {
        int pos = cars[i][0];
        int spd = cars[i][1];
        
        // Calculate time for this car to reach target
        double timeToTarget = (double)(target - pos) / spd;
        
        // If this car takes longer than the current fleet leader,
        // it cannot catch up and must form a new fleet
        if (timeToTarget > lastFleetTime) {
            fleets++;
            lastFleetTime = timeToTarget;
        }
    }
    
    return fleets;
}

6. Java Solution

import java.util.*;

public class CarFleet {
    public int carFleet(int target, int[] position, int[] speed) {
        // Create pairs of (position, speed) and sort by position in descending order
        int n = position.length;
        int[][] cars = new int[n][2];
        
        for (int i = 0; i < n; i++) {
            cars[i][0] = position[i];
            cars[i][1] = speed[i];
        }
        
        // Sort by position in descending order (closer to target first)
        Arrays.sort(cars, (a, b) -> Integer.compare(b[0], a[0]));
        
        Stack<Double> fleets = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            int pos = cars[i][0];
            int spd = cars[i][1];
            
            // Calculate time to reach target
            double timeToTarget = (double)(target - pos) / spd;
            
            // If current car can catch up to the fleet ahead, it joins that fleet
            // Otherwise, it forms a new fleet
            if (fleets.isEmpty() || fleets.peek() < timeToTarget) {
                fleets.push(timeToTarget);
            }
        }
        
        return fleets.size();
    }
}

This solution uses a stack-based approach to track fleet formation. Cars are sorted by position in descending order (closest to target first), then we process each car from front to back. For each car, we calculate how long it takes to reach the target. If this time is greater than the time of the fleet ahead, the car cannot catch up and forms a new fleet. Otherwise, it merges with the existing fleet ahead.

The stack maintains the latest fleet's arrival time, which allows us to efficiently determine when new fleets form. This approach works because cars cannot overtake each other, so the car that's closer to the target but slower will form its own fleet if it can't catch up to the car ahead of it.

7. Complexity Analysis

Time Complexity: O(n log n)

The dominant cost comes from sorting the cars by position, which takes O(n log n) time. The subsequent iteration through the sorted array is O(n), making the overall time complexity O(n log n).

Space Complexity: O(n)

We create a new array cars to store the position and speed pairs, which requires O(n) space. Additionally, sorting may require O(log n) space depending on the implementation, but this is dominated by the O(n) auxiliary array. Thus, the overall space complexity is O(n).

Why these bounds are correct:

The sorting step is the bottleneck because:

1. We must sort cars by position to process them in the correct order
2. Any comparison-based sorting algorithm requires at least O(n log n) time
3. The linear scan afterward is simply O(n) and doesn't change the asymptotic complexity

Optimality:

This is optimal for the general case because:

• We must examine each car at least once to determine fleet formation
• Sorting is necessary to process cars in the correct order (from back to front)
• No comparison-based algorithm can do better than O(n log n) for this problem structure
• The solution achieves the theoretical lower bound for this class of problems

The complexity analysis assumes that we're using an efficient sorting algorithm like merge sort or quicksort, which provide O(n log n) performance in the average and worst cases.

8. Edge Cases & Pitkins

Edge cases and implementation pitfalls are critical to handle properly in this problem:

Empty Input: When target = 12, position = [], speed = [], the solution should return 0 fleets. This is handled naturally by the algorithm since we process no cars.

Single Car: With one car at position 10 with speed 2, reaching target 12, we should return 1 fleet. The algorithm correctly handles this case by treating it as a single fleet.

Identical Positions: If multiple cars start at the same position, they form one fleet. The algorithm handles this by sorting by position first, so cars at the same position are processed together.

Same Speed: Cars with identical speeds but different positions can form multiple fleets. For example, cars at position 1 and 5 with speed 2 reach target 12 at times 5.5 and 3.5 respectively, forming two fleets.

Same Position/Speed: Cars at same position and speed form one fleet. This is handled by the sorting logic that groups cars by position.

Integer Overflow: When calculating arrival times, we must use double to prevent overflow when computing distance / speed. Using integer division would lose precision and cause incorrect fleet grouping.

Misunderstanding of Fleet Formation: A key pitfall is assuming cars form a fleet if they're close in position. The correct logic is that cars form a fleet if the car behind takes longer to reach the target than the car in front - they cannot overtake.

Incorrect Sorting: If we don't sort by position in descending order (closest to target first), we process cars in the wrong sequence, which can cause incorrect fleet formation.

Division by Zero: Though not an issue in this problem since all speeds are positive, it's a general pitfall to ensure we never divide by zero in time calculations.

Misunderstanding Target Distance: The problem requires calculating how many cars reach the target, not how many cars are in front of others. The solution correctly focuses on arrival times and fleet formation logic.

The most common mistake is not properly handling the case where cars at different positions but same arrival times form a single fleet - this is correctly addressed by our sorting and comparison logic.

9. Alternative Approaches

There are several alternative approaches to solving the Car Fleet problem, each with different trade-offs:

1. Simulation Approach: Instead of sorting and analyzing positions, we could simulate the movement of cars forward in time. We'd maintain a timeline of events and process collisions as they occur. This approach would be O(n²) in the worst case due to collision detection between all cars, and is not recommended for this problem.

2. Stack-based Approach: We could use a stack to simulate the formation of fleets by processing cars in reverse order (from closest to target). For each car, if it can catch up to the fleet at the top of stack, it joins that fleet; otherwise, it forms a new fleet. This is O(n log n) due to sorting but uses additional stack space.

3. Two-pointer Technique: If we were to process cars in a specific order, we could potentially use two pointers to track fleet formation. However, this requires careful ordering and is more complex than the sorting-based approach.

4. Priority Queue Approach: We could use a priority queue to process cars by their positions, but this would still require sorting and doesn't provide significant advantages over the direct sorting approach.

The chosen solution using sorting is optimal for this problem because:

• It's intuitive and easy to understand
• It has optimal time complexity O(n log n) due to the sorting requirement
• It's space-efficient with minimal additional overhead
• The logic flow is clean and maintainable

The sorting approach is superior because it naturally handles the problem's core constraint that cars cannot overtake each other, making it the most practical and efficient solution for this specific problem domain.

10. Test Cases

public class CarFleetTestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic case from problem description
        // Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
        // Expected: 3 fleets
        int target1 = 12;
        int[] position1 = {10,8,0,5,3};
        int[] speed1 = {2,4,1,1,3};
        System.out.println("Test 1 - Expected: 3, Actual: " + carFleet(target1, position1, speed1));
        
        // Test Case 2: Empty input
        // Input: target = 10, position = [], speed = []
        // Expected: 0 fleets
        int target2 = 10;
        int[] position2 = {};
        int[] speed2 = {};
        System.out.println("Test 2 - Expected: 0, Actual: " - carFleet(target2, position2, speed2));
        
        // Test Case 3: Single car
        // Input: target = 10, position = [5], speed = [1]
        // Expected: 1 fleet
        int target3 = 10;
        int[] position3 = {5};
        int[] speed3 = {1};
        System.out.println("Test 3 - Expected: 1, Actual: " + carFleet(target3, position3, speed3));
        
        // Test Case 4: Cars at same position
        // Input: target = 10, position = [5,5,5], speed = [2,3,4]
        // Expected: 1 fleet (all merge into one)
        int target4 = 10;
        int[] position4 = {5,5,5};
        int[] speed4 = {2,3,4};
        System.out.println("Test 4 - Expected: 1, Actual: " + carFleet(target4, position4, speed4));
        
        // Test Case 5: Cars moving at same speed
        // Input: target = 10, position = [0,2,4], speed = [5,5,5]
        // Expected: 3 fleets (no merging possible)
        int target5 = 10;
        int[] position5 = {0,2,4};
        int[] speed5 = {5,5,5};
        System.out.println("Test 5 - Expected: 3, Actual: " + carFleet(target5, position5, speed5));
        
        // Test Case 6: Complex case with merging
        // Input: target = 100, position = [0,2,4], speed = [1,3,2]
        // Expected: 2 fleets (car at position 0 and 2 merge into one, car at 4 stays separate)
        int target6 = 100;
        int[] position6 = {0,2,4};
        int[] speed6 = {1,3,2};
        System.out.println("Test 6 - Expected: 2, Actual: " + carFleet(target6, position6, speed6));
    }
}

11. Final Summary

The Car Fleet problem is elegantly solved by sorting cars by position and calculating their arrival times. The key insight is that cars cannot overtake, so we process from the car closest to the target backward. When a car's arrival time is greater than or equal to the current fleet's arrival time, it forms a new fleet. This greedy approach ensures optimal solution with O(n log n) time complexity due to sorting, which is optimal for this problem since we must examine all cars at least once.

11. Final Summary

The core insight is to sort cars by position and process them from the furthest to closest to the target, using a stack-like approach to track fleet formations. By maintaining the time each car would take to reach the target, we can efficiently determine when cars merge into fleets based on their arrival times. This greedy approach works because cars cannot overtake, so the car at the back of a fleet will always determine when that entire fleet reaches the target. The solution is optimal with O(n log n) time complexity due to sorting, which is necessary since we must process cars in order of their starting positions to correctly simulate the traffic flow.