Car Fleet II - Practice Coding Problems

Car Fleet II - Problem

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [position_i, speed_i] represents:

position_i is the distance between the i^th car and the beginning of the road in meters. It is guaranteed that position_i < position_i+1.
speed_i is the initial speed of the i^th car in meters per second.

For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the i^th car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10^-5 of the actual answers are accepted.

Input & Output

Example 1 — Basic Case

$ Input: cars = [[1,2],[3,1],[5,3]]

› Output: [2.0,-1,-1]

💡 Note: Car 0 (pos=1, speed=2) catches Car 1 (pos=3, speed=1) at time (3-1)/(2-1) = 2.0. Car 1 cannot catch Car 2 (slower speed). Car 2 is last.

Example 2 — No Collisions

$ Input: cars = [[1,1],[2,2],[3,3]]

› Output: [-1,-1,-1]

💡 Note: Each car is slower than the one ahead, so no collisions occur. All return -1.

Example 3 — Multiple Collisions

$ Input: cars = [[1,4],[2,3],[4,1]]

› Output: [0.5,1.0,-1]

💡 Note: Car 0 catches Car 1 at time (2-1)/(4-3) = 1.0. Car 1 catches Car 2 at time (4-2)/(3-1) = 1.0. Car 2 is last.

Constraints

1 ≤ cars.length ≤ 10⁵
1 ≤ position_i, speed_i ≤ 10⁶
position_i < position_i+1

Visualization

Tap to expand

Understanding the Visualization

Input

Cars with positions and speeds on a road

Process

Calculate collision times considering fleet formation

Output

Array of collision times or -1 for no collision

Key Takeaway

🎯 Key Insight: Process cars right-to-left with a stack to handle complex fleet collision chains

Asked in

G Google 15 a Amazon 12 M Microsoft 8 A Apple 6

The key insight is to process cars from right to left using a monotonic stack to handle fleet formations. Cars can only collide with cars ahead of them, and when fleets form, they move at the slowest car's speed. Best approach uses monotonic stack: Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack	O(n)	O(n)	Use a stack to process cars from right to left, handling fleet formations
Brute Force Simulation	O(n)	O(1)	For each car, simulate movement and check when it collides with the next car

Monotonic Stack — Algorithm Steps

Process cars from right to left
Maintain stack of cars that can be collision targets
For each car, pop invalid targets from stack
Calculate collision time with valid target

Visualization

Tap to expand

Step-by-Step Walkthrough

Right-to-Left

Process cars from rightmost to leftmost

Stack Management

Remove invalid targets, calculate collision times

Chain Reaction

Handle fleet formations and collision chains

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double* solution(int cars[][2], int n, int* returnSize) {
    *returnSize = n;
    double* result = (double*)malloc(n * sizeof(double));
    int* stack = (int*)malloc(n * sizeof(int));
    int stackTop = -1;
    
    // Initialize result with -1
    for (int i = 0; i < n; i++) {
        result[i] = -1;
    }
    
    // Process from right to left
    for (int i = n - 1; i >= 0; i--) {
        int posI = cars[i][0], speedI = cars[i][1];
        
        // Remove cars from stack that car i cannot catch
        while (stackTop >= 0) {
            int j = stack[stackTop];
            int posJ = cars[j][0], speedJ = cars[j][1];
            
            if (speedI <= speedJ) {
                // Car i is not faster, cannot catch car j
                break;
            }
            
            // Calculate collision time between car i and car j
            double collisionTime = (double)(posJ - posI) / (speedI - speedJ);
            
            // If car j will collide with another car before car i reaches it
            if (result[j] != -1 && result[j] <= collisionTime) {
                stackTop--;  // Car j will be gone
            } else {
                // Car i will collide with car j
                result[i] = collisionTime;
                break;
            }
        }
        
        stack[++stackTop] = i;
    }
    
    free(stack);
    return result;
}

int main() {
    // Simple parsing for demo - assumes format [[a,b],[c,d]]
    int cars[100][2];
    int n = 0;
    
    // Read and parse input (simplified)
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Basic parsing - this is simplified for the example
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            cars[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            cars[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    int returnSize;
    double* result = solution(cars, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%g", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each car is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n cars in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler