18-Car-Fleet.md

Car Fleet

Problem Link

https://leetcode.com/problems/car-fleet/

---

Pattern

• Stack
• Sorting

---

Approach

Sort cars by starting position and merge them into fleets based on arrival times.

---

Time Complexity

O(n log n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        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];
        }
        Arrays.sort(cars, (a, b) -> b[0] - a[0]);
        int fleets = 0;
        double last = 0;
        for (int[] car : cars) {
            double time = (double)(target - car[0]) / car[1];
            if (time > last) {
                fleets++;
                last = time;
            }
        }
        return fleets;
    }
}