Start learning free

LESSON 416 OF 573 · STACK

Car Fleet in Kotlin: O(n log n) with Sorting and a Stack

Practice O(n log n) Read the full explanation

There are n cars on a one-lane road, all driving to the same destination, target miles from the start of the road. You are given two arrays of n integers, position and speed: car i starts at mile position[i] and drives at speed[i] miles per hour.

A car can never pass the car ahead of it. When it catches up with a slower car, it slows down and the two drive on together, bumper to bumper, at the speed of the car in front. A car fleet is a group of cars driving together like this; a car that drives alone is a fleet too. A car that catches up with a fleet exactly at target is part of that fleet.

Return the number of car fleets that arrive at target.

 

Example 1:

Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Explanation:
- The car from mile 10 would arrive after (12 - 10) / 2 = 1 hour, and so would the car from mile 8,
  after (12 - 8) / 4 = 1 hour. The second one catches up with the first exactly at the target: one fleet.
- The car from mile 5 (speed 1) would need 7 hours, the car from mile 3 (speed 3) only 3. They meet at
  mile 6 after 1 hour and drive on together at speed 1: a second fleet, arriving after 7 hours.
- The car from mile 0 (speed 1) would need 12 hours and never catches up with anyone: a third fleet.

Example 2:

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: A single car is one fleet.

Example 3:

Input: target = 100, position = [0, 2, 4], speed = [4, 2, 1]
Output: 1
Explanation: The car from mile 0 catches up with the car from mile 2 at mile 4, after 1 hour,
and they drive on at speed 2. That fleet catches up with the car from mile 4 at mile 6, after 2 hours, and
all three drive on at speed 1, arriving together after 96 hours.

 

Constraints:

  • n is the length of both position and speed
  • 1 <= n <= 105
  • 1 <= target <= 106
  • 0 <= position[i] < target
  • All the values in position are different.
  • 1 <= speed[i] <= 106

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.



Only the order of the cars on the road matters, so visit them from the one closest to the target to the one farthest from it. If nothing slowed it down, car i would arrive after (target - position[i]) / speed[i] hours. A car that would arrive no later than the fleet just ahead of it catches up with that fleet, at the latest at the target, and joins it. A car that would arrive later never catches up: it starts a new fleet, which the cars behind it may join.

Keep the fleets found so far on a stack. A fleet arrives when the car that leads it would arrive on its own, since that car was never slowed down. The fleet just ahead of the next car is always the one on top of the stack, and it is also the one that arrives last: compare the car with it only. A car that would arrive later starts a new fleet and goes on top; otherwise it joins the top fleet. The answer is the size of the stack.

The times are fractions. Compare them exactly, without dividing: since the speeds are positive, (target - p1) / s1 > (target - p2) / s2 is the same as (target - p1) * s2 > (target - p2) * s1. These products can reach 1012, more than a 32-bit integer holds: where integers are 32 bits, compute them with 64-bit integers. A Python integer, or a JavaScript or TypeScript number (exact for whole numbers below 253), holds them as it is.

Sorting the cars by position takes O(n log n) time. The pass over the sorted cars does a constant amount of work for each car, so sorting is the larger part. The sorted order and the stack hold at most n cars each: O(n) extra space.
STEP 1 OF 8
    Ctrl + Enter to check

    KOTLIN · STACK

    Car Fleet in Kotlin, explained

    Problem overview

    Cars drive on a one-lane road to a destination target miles from the start. Car i starts at mile position[i] and drives at speed[i] miles per hour. A car can't pass the car ahead: when it catches up, it slows down and the two drive on together at the front car's speed. A group of cars driving together is a fleet, and a car on its own is a fleet too. A car that catches up exactly at target still belongs to the fleet it reached. The method returns how many fleets arrive.

    In the first example, target = 12, position = [10, 8, 0, 5, 3] and speed = [2, 4, 1, 1, 3], the answer is 3. The cars from miles 10 and 8 would both arrive after 1 hour, so they form one fleet. The cars from miles 5 and 3 meet and drive on at speed 1, arriving after 7 hours: a second fleet. The car from mile 0 never catches anyone: a third.

    Approach

    Simulating the road minute by minute, or checking every pair of cars, is slow and awkward. The key idea is to look only at the time each car would need if nothing slowed it down: (target - position[i]) / speed[i] hours.

    Look at the cars from the one closest to the target to the farthest. The closest car can never be blocked. Each next car can only meet the cars ahead of it, and those are already handled. The fleet just ahead of the current car is always the last one found so far, and it is also the one that arrives last. So compare the car with that fleet only:

    • If the car would arrive no later than that fleet, it catches up with it at the latest at the target and joins it. Nothing to do.
    • If the car would arrive later, it can't catch up. It leads a new fleet, and the cars behind it may still join this new one.

    A fleet arrives when the car that leads it would arrive on its own, since that car was never slowed down, so the stack only needs the number of the lead car of each fleet. The answer is the size of the stack. Sorting the cars by position costs O(n log n), and the pass after it is O(n).

    The times are fractions, so the lesson compares them without dividing, as explained below.

    Step by step

    1. Sort the car numbers. val order = position.indices.sortedByDescending { position[it] }. position.indices is the range of the indexes, and sortedByDescending returns them as a new list, largest key first. The key is the car's position, so the car closest to the target comes first. Sorting car numbers rather than positions keeps each position tied to its speed.
    2. The stack. val fleets = ArrayDeque<Int>() holds, for each fleet, the number of its lead car. The last element is the top.
    3. The loop. for (car in order) visits the cars from front to back.
    4. New fleet or not. Inside, an if checks fleets.isEmpty() || arrivesLater(target, position, speed, car, fleets.last()). The || stops at the first true part, so last() is only read when the stack isn't empty.
    5. Push. In that if, fleets.addLast(car): the car leads a new fleet.
    6. Answer. After the loop, return fleets.size.
    7. The helper. arrivesLater takes target, position, speed, car and lead, and answers whether car, driving alone, would arrive strictly later than lead. Strictly, because a car that arrives at the same moment joins the fleet.
    8. The comparison. It multiplies both sides of the time comparison by the two speeds, which are positive, and compares (target - position[car]).toLong() * speed[lead] with (target - position[lead]).toLong() * speed[car].

    The solution in Kotlin

    class Solution {
    fun carFleet(target: Int, position: IntArray, speed: IntArray): Int {
        val order = position.indices.sortedByDescending { position[it] }
        val fleets = ArrayDeque<Int>()
        for (car in order) {
            if (fleets.isEmpty() || arrivesLater(target, position, speed, car, fleets.last())) {
                fleets.addLast(car)
            }
        }
        return fleets.size
    }

    fun arrivesLater(target: Int, position: IntArray, speed: IntArray, car: Int, lead: Int): Boolean {
        return (target - position[car]).toLong() * speed[lead] > (target - position[lead]).toLong() * speed[car]
    }
}

    Why compare without dividing, and why toLong()

    The comparison (target - position[car]) / speed[car] > (target - position[lead]) / speed[lead] is the same as the cross-multiplied one, because both speeds are positive. Cross-multiplying keeps the times exact: equal times stay exactly equal, with no rounding.

    The two ways around it both fail:

    • Integer division. In Kotlin, Int / Int truncates. Take target = 13 with a lead car at mile 10 and speed 2 (1.5 hours) and a car at mile 8 with speed 3 (1.6666666666666667 hours). The second would arrive later and starts its own fleet, so the answer is 2. But (13 - 8) / 3 == (13 - 10) / 2 is true, since both truncate to 1, and a solution using integer division merges the cars into one fleet.
    • Overflow. Each product can reach about a trillion (10^12), far beyond what an Int (32 bits, about 2.1 billion) holds, and Int overflow wraps silently. For example, (1_000_000 - 0) * 1_000_000 in Int prints -727379968. With target = 1_000_000, position = [0, 999_999] and speed = [1, 1_000_000], the rear car needs 1,000,000 hours and the front car 0.000001 hours, so the rear car arrives later and the answer is 2. The cross-multiplied comparison in Long says so (true), but the same comparison in Int says false.

    .toLong() on the first factor makes the multiplication happen in 64 bits, because a Long times an Int is a Long. The subtraction inside the parentheses is done on Ints first, and that is safe: it is at most a million.

    A trace

    For the first example, order is [0, 1, 3, 4, 2]: the cars from miles 10, 8, 5, 3 and 0. Their times alone are 1.0, 1.0, 7.0, 3.0 and 12.0 hours.

    1. The car from mile 10 starts the stack: one fleet, lead time 1.0.
    2. The car from mile 8 also takes 1.0, which is not strictly later, so it joins.
    3. The car from mile 5 takes 7.0, later than 1.0: a new fleet.
    4. The car from mile 3 takes 3.0, not later than 7.0: it joins the fleet of mile 5.
    5. The car from mile 0 takes 12.0, later than 7.0: a third fleet.

    The method returns 3.

    Complexity

    Time: O(n log n). Sorting costs O(n log n). The loop does a constant amount of work per car, so sorting is the larger part.

    Space: O(n). The sorted list of car numbers and the stack each hold at most n entries.

    Edge cases and common mistakes

    • Sorting the positions only. If you sort position on its own, the speeds no longer match. Sort the car numbers by position instead.
    • Using the wrong direction. The loop must start with the car closest to the target. Going from the back would compare each car with a car it has not yet had to deal with.
    • Using >= in the helper. A car that arrives at exactly the same time as the fleet ahead belongs to it (the first two cars of the first example). The check must be strict.
    • Cars with equal speed. They never meet unless they share a position, and positions are all different. For target = 10, position = [0, 5] and speed = [1, 1] the answer is 2.
    • A single car is one fleet: carFleet(10, intArrayOf(3), intArrayOf(3)) returns 1.
    • Dividing as Int or overflowing, as shown above.

    Testing

    These calls were run against the solution above:

    targetpositionspeedResult
    12[10, 8, 0, 5, 3][2, 4, 1, 1, 3]3
    10[3][3]1
    100[0, 2, 4][4, 2, 1]1
    10[0, 4, 2][2, 1, 3]1
    10[6, 8][3, 2]2
    10[0, 5][1, 1]2
    13[10, 8][2, 3]2
    1000000[0, 999999][1, 1000000]2
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free