Skip to main content
CodePeetCodePeet
CodePeet 250

Car Pooling

MEDIUMProblemSolveExternal Links

Description

You have a car with a fixed number of empty seats, given by capacity. The car travels only eastward along a straight road — it cannot turn around.

You are given an array trips where each element trips[i] = [numPassengers, from, to] describes a single trip:

  • numPassengers passengers need to be picked up at kilometre from.
  • Those passengers must be dropped off at kilometre to.

The car picks up passengers at the from location and drops them off at the to location (they are no longer in the car at to).

Return true if it is possible to complete all trips without ever exceeding the car's capacity at any point along the route. Return false otherwise.

Examples

Example 1

Input: trips = [[2,1,5],[3,3,7]], capacity = 4

Output: false

Explanation: At kilometre 1, we pick up 2 passengers (car has 2). At kilometre 3, we pick up 3 more (car now has 5). But 5 exceeds the capacity of 4, so we cannot complete all trips.

Example 2

Input: trips = [[2,1,5],[3,3,7]], capacity = 5

Output: true

Explanation: At kilometre 1, pick up 2 passengers (car has 2). At kilometre 3, pick up 3 more (car has 5, which equals the capacity — still valid). At kilometre 5, drop off the first 2 (car has 3). At kilometre 7, drop off the remaining 3 (car has 0). The capacity is never exceeded.

Example 3

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11

Output: true

Explanation: At km 2, pick up 3 (car has 3). At km 3, pick up 8 (car has 11, equals capacity). At km 7, drop off the first 3 AND pick up 3 new ones (the drop-off happens first conceptually since passengers leave at their destination). Car has 11. At km 9, drop off 3 + 8 = 11 (car has 0). Capacity is never exceeded.

Constraints

  • 1 ≤ trips.length ≤ 1000
  • trips[i].length == 3
  • 1 ≤ numPassengers ≤ 100
  • 0 ≤ from < to ≤ 1000
  • 1 ≤ capacity ≤ 10^5

Editorial

Brute Force

Intuition

The most direct way to think about this problem is to simulate the car's journey kilometre by kilometre. At each location along the route, count how many passengers are currently in the car, and check whether that count exceeds the capacity.

Imagine you are driving a shuttle bus down a straight road. At every kilometre marker, you look at your manifest: which trips have started but not yet ended at this point? You add up those passengers and make sure you are not overloaded.

For each location from 0 to the farthest drop-off, we loop through all trips and check whether the location falls within the trip's active range — that is, from ≤ location < to. If it does, we add the trip's passenger count to the running total for that location.

Step-by-Step Explanation

Let us trace with trips = [[2,1,5],[3,3,7]], capacity = 4.

Step 1: Find the maximum drop-off location: max(5, 7) = 7. We check locations 0 through 6 (passengers leave AT the drop-off, so they are in the car from from to to - 1).

Step 2: Location 0 — For trip [2,1,5]: 0 < 1, not active. For trip [3,3,7]: 0 < 3, not active. Passengers = 0. OK.

Step 3: Location 1 — For trip [2,1,5]: 1 ≥ 1 and 1 < 5, active → +2. For trip [3,3,7]: 1 < 3, not active. Passengers = 2 ≤ 4. OK.

Step 4: Location 2 — Trip [2,1,5] active → +2. Trip [3,3,7] not active. Passengers = 2 ≤ 4. OK.

Step 5: Location 3 — Trip [2,1,5]: 3 ≥ 1 and 3 < 5, active → +2. Trip [3,3,7]: 3 ≥ 3 and 3 < 7, active → +3. Passengers = 5. 5 > 4 — EXCEEDS CAPACITY!

Step 6: We found a violation at location 3. Return false immediately.

Result: false — the car cannot handle all trips with capacity 4.

Brute Force Simulation — Checking Passengers at Each Location — Watch how we check every location along the route, summing up active trips at each point to determine whether the car's capacity is exceeded.

Algorithm

  1. Find the maximum drop-off location M across all trips.
  2. For each location loc from 0 to M - 1:
    a. Initialize passengers = 0.
    b. For each trip [num, from, to]:
    • If from ≤ loc < to, add num to passengers.
      c. If passengers > capacity, return false.
  3. If no location exceeds capacity, return true.

Code

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int maxLoc = 0;
        for (auto& t : trips) {
            maxLoc = max(maxLoc, t[2]);
        }

        for (int loc = 0; loc < maxLoc; loc++) {
            int passengers = 0;
            for (auto& t : trips) {
                if (t[1] <= loc && loc < t[2]) {
                    passengers += t[0];
                }
            }
            if (passengers > capacity) return false;
        }
        return true;
    }
};
class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        max_loc = max(t[2] for t in trips)

        for loc in range(max_loc):
            passengers = 0
            for num, frm, to in trips:
                if frm <= loc < to:
                    passengers += num
            if passengers > capacity:
                return False

        return True
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int maxLoc = 0;
        for (int[] t : trips) {
            maxLoc = Math.max(maxLoc, t[2]);
        }

        for (int loc = 0; loc < maxLoc; loc++) {
            int passengers = 0;
            for (int[] t : trips) {
                if (t[1] <= loc && loc < t[2]) {
                    passengers += t[0];
                }
            }
            if (passengers > capacity) return false;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(M · n)

Where M is the maximum drop-off location (up to 1000) and n is the number of trips (up to 1000). For every location we scan all trips, giving up to 1,000,000 operations in the worst case. This is acceptable for the given constraints but far from optimal.

Space Complexity: O(1)

We only use a few integer variables. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force checks every (location, trip) pair, doing O(M · n) work. Most of this work is wasted — at a given location, most trips are not active, but we still inspect every single one.

The fundamental inefficiency is that we recount passengers from scratch at every location. If we knew how the passenger count changes from one location to the next, we could process the changes incrementally instead of re-summing everything.

Key insight: the passenger count only changes at event points — pickup locations (count goes up) and drop-off locations (count goes down). Between events, the count stays the same. We can sort these events and sweep through them, which avoids rechecking inactive trips.

Better Approach - Sort Events and Sweep

Intuition

Instead of checking every location, we only care about the points where passengers get on or off. We can model each trip as two events:

  • A pickup event at location from: the passenger count increases by numPassengers.
  • A drop-off event at location to: the count decreases by numPassengers.

Think of a bus schedule board. Instead of watching the bus at every kilometre, you just look at the stops. At each stop, you note who gets on and who gets off, then update the running total.

We collect all these events, sort them by location, and sweep through in order. At each event, we update a running passenger count and check if it exceeds the capacity. Sorting ensures we process events left to right along the route.

An important detail: when a pickup and a drop-off happen at the same location, the drop-off should be processed first (passengers leave before new ones board). This is handled naturally because the problem states passengers are no longer in the car at their to location.

Step-by-Step Explanation

Let us trace with trips = [[2,1,5],[3,3,7]], capacity = 4.

Step 1: Create events from each trip:

  • Trip [2,1,5] → event (loc=1, +2) and event (loc=5, -2).
  • Trip [3,3,7] → event (loc=3, +3) and event (loc=7, -3).
  • All events: [(1,+2), (3,+3), (5,-2), (7,-3)].

Step 2: Sort events by location (already sorted here): [(1,+2), (3,+3), (5,-2), (7,-3)].

Step 3: Start sweep with current_passengers = 0.

Step 4: Process event (1, +2): current_passengers = 0 + 2 = 2. Check: 2 ≤ 4? Yes. OK.

Step 5: Process event (3, +3): current_passengers = 2 + 3 = 5. Check: 5 ≤ 4? NO — exceeds capacity!

Step 6: Return false immediately.

Result: false.

Event Sweep — Processing Pickups and Drop-offs in Order — Watch how we convert trips into sorted events and sweep through them, maintaining a running passenger count that reveals capacity violations.

Algorithm

  1. Create a list of events. For each trip [num, from, to]:
    • Add event (from, +num) (pickup).
    • Add event (to, -num) (drop-off).
  2. Sort events by location. If two events share the same location, process drop-offs (negative) before pickups (positive).
  3. Initialize current_passengers = 0.
  4. For each event (loc, change):
    • Update current_passengers += change.
    • If current_passengers > capacity, return false.
  5. Return true.

Code

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<pair<int,int>> events;
        for (auto& t : trips) {
            events.push_back({t[1], t[0]});   // pickup
            events.push_back({t[2], -t[0]});  // drop-off
        }

        // Sort by location; at same location, drop-offs before pickups
        sort(events.begin(), events.end(), [](auto& a, auto& b) {
            return a.first == b.first ? a.second < b.second : a.first < b.first;
        });

        int passengers = 0;
        for (auto& [loc, change] : events) {
            passengers += change;
            if (passengers > capacity) return false;
        }
        return true;
    }
};
class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        events = []
        for num, frm, to in trips:
            events.append((frm, num))    # pickup
            events.append((to, -num))    # drop-off

        # Sort by location; at same location, drop-offs (negative) first
        events.sort(key=lambda x: (x[0], x[1]))

        passengers = 0
        for loc, change in events:
            passengers += change
            if passengers > capacity:
                return False

        return True
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        List<int[]> events = new ArrayList<>();
        for (int[] t : trips) {
            events.add(new int[]{t[1], t[0]});    // pickup
            events.add(new int[]{t[2], -t[0]});   // drop-off
        }

        // Sort by location; at same location, drop-offs first
        events.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        int passengers = 0;
        for (int[] event : events) {
            passengers += event[1];
            if (passengers > capacity) return false;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

We create 2n events and sort them, costing O(n log n). The sweep through sorted events is O(n). The sort dominates.

Space Complexity: O(n)

We store 2n events in a list.

Why This Approach Is Not Efficient

The event sweep runs in O(n log n) due to sorting, which is already very efficient. However, we can observe that the problem has a special property: all locations are integers in a bounded range (0 ≤ location ≤ 1000). When the range of values is small and fixed, we can avoid comparison-based sorting entirely.

Instead of sorting events, we can use a difference array — a fixed-size array indexed by location — to record the net passenger change at each point. Then a single prefix-sum pass over this array gives us the passenger count at every location. This eliminates the O(n log n) sorting step and reduces the total time to O(n + M), where M is the maximum location value (at most 1000).

Optimal Approach - Difference Array

Intuition

Instead of creating event objects and sorting them, we can use the difference array technique. The idea is elegantly simple:

  1. Create an array diff of size M+1 (where M is the farthest drop-off), initialised to all zeros.
  2. For each trip [num, from, to]:
    • Add +num at index from (passengers board).
    • Add -num at index to (passengers exit).
  3. Compute the prefix sum of diff. At each index, the prefix sum tells you the exact number of passengers in the car at that location.
  4. If the prefix sum ever exceeds capacity, return false.

Think of the diff array as a ledger that records only the changes — not the totals. "At km 1, add 2 passengers. At km 5, remove 2 passengers." The prefix sum converts these changes back into running totals.

This technique works because passengers board at a single point and exit at a single point, and the locations are small integers — perfect for array indexing.

Difference array concept: recording +passengers at pickup and -passengers at drop-off, then computing prefix sum
Difference array concept: recording +passengers at pickup and -passengers at drop-off, then computing prefix sum

Step-by-Step Explanation

Let us trace with trips = [[2,1,5],[3,3,7]], capacity = 4.

Step 1: Find max drop-off: max(5, 7) = 7. Create diff array of size 8 (indices 0..7), all zeros: [0, 0, 0, 0, 0, 0, 0, 0].

Step 2: Process trip [2, 1, 5]: diff[1] += 2, diff[5] -= 2. Array: [0, 2, 0, 0, 0, -2, 0, 0].

Step 3: Process trip [3, 3, 7]: diff[3] += 3, diff[7] -= 3. Array: [0, 2, 0, 3, 0, -2, 0, -3].

Step 4: Compute prefix sum and check. Start with running_sum = 0.

  • Index 0: running_sum = 0 + 0 = 0. ≤ 4? Yes.
  • Index 1: running_sum = 0 + 2 = 2. ≤ 4? Yes.
  • Index 2: running_sum = 2 + 0 = 2. ≤ 4? Yes.
  • Index 3: running_sum = 2 + 3 = 5. ≤ 4? NO — exceeds capacity!

Step 5: Return false.

Result: false — same answer, but computed without sorting and without checking inactive trips.

Difference Array — Record Changes, Compute Prefix Sum, Check Capacity — Watch how we record passenger changes in a difference array, then sweep with a prefix sum to find the exact passenger count at each location.

Algorithm

  1. Find the maximum drop-off location M.
  2. Create an integer array diff of size M + 1, initialised to zeros.
  3. For each trip [num, from, to]:
    • diff[from] += num (passengers board).
    • diff[to] -= num (passengers exit).
  4. Compute the prefix sum of diff. At each index, check whether the prefix sum exceeds capacity.
    • If it does, return false.
  5. If the entire prefix sum stays within capacity, return true.

Code

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int maxLoc = 0;
        for (auto& t : trips) {
            maxLoc = max(maxLoc, t[2]);
        }

        vector<int> diff(maxLoc + 1, 0);
        for (auto& t : trips) {
            diff[t[1]] += t[0];  // passengers board
            diff[t[2]] -= t[0];  // passengers exit
        }

        int passengers = 0;
        for (int i = 0; i <= maxLoc; i++) {
            passengers += diff[i];
            if (passengers > capacity) return false;
        }
        return true;
    }
};
from itertools import accumulate

class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        max_loc = max(t[2] for t in trips)
        diff = [0] * (max_loc + 1)

        for num, frm, to in trips:
            diff[frm] += num   # passengers board
            diff[to] -= num    # passengers exit

        return all(s <= capacity for s in accumulate(diff))
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int maxLoc = 0;
        for (int[] t : trips) {
            maxLoc = Math.max(maxLoc, t[2]);
        }

        int[] diff = new int[maxLoc + 1];
        for (int[] t : trips) {
            diff[t[1]] += t[0];  // passengers board
            diff[t[2]] -= t[0];  // passengers exit
        }

        int passengers = 0;
        for (int i = 0; i <= maxLoc; i++) {
            passengers += diff[i];
            if (passengers > capacity) return false;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n + M)

Where n is the number of trips and M is the maximum drop-off location. We iterate through all trips once to populate the difference array (O(n)), then sweep through the array to compute the prefix sum (O(M)). Since M ≤ 1000 is bounded by the constraints, the effective time complexity is O(n).

Space Complexity: O(M)

The difference array has M + 1 entries. Since M ≤ 1000, this is at most 1001 integers — effectively constant space relative to n. No sorting is needed, no event objects are created.