Car Pooling

Medium Intervals Line Sweep Original on LeetCode

Car Pooling is a medium intervals problem solved with the line sweep pattern. The best approach, optimal (line sweep with a difference array), runs in O(n + L) time and O(L) space. Below are 2 approaches in Java, from simulate every kilometre up.

Problem

A car with capacity seats drives east. Each trip [passengers, from, to] picks up passengers at kilometre from and drops them at to. Decide whether all trips can be completed without exceeding capacity at any point.

Examples

Example 1

Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Output: false
Why: Between km 3 and 5 there are 5 passengers.

Example 2

Input: trips = [[2, 1, 5], [3, 5, 7]], capacity = 3
Output: true
Why: The first group leaves at 5, just as the second group boards.

Constraints

1 <= trips.length <= 1000; trip = [passengers, from, to].
0 <= from < to <= 1000; the car only drives east.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Simulate every kilometre	`O(n · L)`	`O(L)`
Optimal (line sweep with a difference array)	`O(n + L)`	`O(L)`

1Simulate every kilometre

TimeO(n · L)L = route length (up to 1000).

SpaceO(L)

For each trip, add its passengers to every kilometre from from to to - 1, then check whether any kilometre exceeds capacity.

load[km] += p for km in [from, to).
Return false if any load > capacity.

Java

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] load = new int[1001];
        for (int[] t : trips)
            for (int km = t[1]; km < t[2]; km++) load[km] += t[0];
        for (int x : load) if (x > capacity) return false;
        return true;
    }
}

2Optimal (line sweep with a difference array)

TimeO(n + L)

SpaceO(L)

Only the change in passengers matters: +p at from, -p at to. A running sum over positions gives the load at each point. Drop-offs at a point are applied before that point's pick-ups because both are summed into the same cell.

diff[from] += p; diff[to] -= p.
Running sum; if it exceeds capacity, return false.

Java

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] t : trips) {
            diff[t[1]] += t[0];
            diff[t[2]] -= t[0];
        }
        int load = 0;
        for (int d : diff) {
            load += d;
            if (load > capacity) return false;
        }
        return true;
    }
}

Edge cases to test

Drop-off and pick-up at the same point
One trip larger than the capacity

Hints

Hint 1

Record +passengers at each pick-up point and -passengers at each drop-off point, then take a running sum.

FAQ

What is the best time complexity for Car Pooling?

Optimal (line sweep with a difference array) runs in O(n + L) time and O(L) extra space.

Which pattern does Car Pooling use?

It is a intervals problem that uses the line sweep pattern. Other problems with the same pattern: Meeting Rooms II.

Is there a brute force solution for Car Pooling?

Yes. Simulate every kilometre takes O(n · L) time and O(L) space. For each trip, add its passengers to every kilometre from from to to - 1, then check whether any kilometre exceeds capacity.

Which edge cases should I test for Car Pooling?

Drop-off and pick-up at the same point; One trip larger than the capacity.