Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Car Pooling
• Topics: Array, Sorting, Heap (Priority Queue), Simulation, Prefix Sum

What the problem is really asking

A car has a fixed number of seats and only travels east. Each trip is described as [passengers, pickup, dropoff]: the passengers enter at pickup and leave at dropoff.

The task is to decide whether every requested trip can be completed without the number of passengers in the car ever exceeding its capacity.

The important detail is that the car moves in one direction. That turns the route into a timeline. At each location, only two kinds of events matter:

• Some passengers get in.
• Some passengers get out.

There is no need to simulate each passenger or each trip separately while the car moves. The algorithm only needs to know the net change at every location.

Deriving the prefix-sum solution

Suppose a trip is [3, 2, 7]. Three passengers enter at location 2 and leave at location 7.

Represent that trip with two changes:

• Add 3 at location 2.
• Subtract 3 at location 7.

After recording the changes for every trip, scan the route from west to east and keep a running passenger count. The running total is a prefix sum: after applying the change at a location, it equals the number of passengers currently in the car.

This also handles dropoffs and pickups at the same location correctly. A dropoff contributes a negative change and a pickup contributes a positive change. Their combined delta reflects the occupancy after both events have been processed.

For example, with trips [[2, 1, 5], [3, 3, 7]], the relevant changes are:

location 1: +2
location 3: +3
location 5: -2
location 7: -3

The running passenger counts are 2, 5, 3, and 0. If the car has fewer than 5 seats, the trips cannot all be completed.

Why the solution works

Every trip affects the occupied-seat count on one continuous half-open interval: from its pickup location up to, but not including, its dropoff location.

Adding the passenger count at the pickup point starts that interval. Subtracting the same count at the dropoff point ends it. Therefore, the prefix sum at each location is exactly the number of passengers whose trips are active there.

If any prefix sum is greater than the car’s capacity, too many passengers need seats at that point and the answer is False. If every prefix sum stays within capacity, every pickup can be served and the answer is True.

Python solution

from typing import List, Sequence


def build_passenger_deltas(trips: Sequence[Sequence[int]]) -> List[int]:
    """Return the net passenger-count change at each route location."""
    if not trips:
        return []

    final_location = max(dropoff_location for _, _, dropoff_location in trips)
    passenger_deltas = [0] * (final_location + 1)

    for passenger_count, pickup_location, dropoff_location in trips:
        passenger_deltas[pickup_location] += passenger_count
        passenger_deltas[dropoff_location] -= passenger_count

    return passenger_deltas


def can_complete_all_trips(
    trips: Sequence[Sequence[int]],
    seat_capacity: int,
) -> bool:
    """Return whether the car can serve every trip without exceeding capacity."""
    current_passengers = 0

    for passenger_delta in build_passenger_deltas(trips):
        current_passengers += passenger_delta
        if current_passengers > seat_capacity:
            return False

    return True


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        return can_complete_all_trips(
            trips=trips,
            seat_capacity=capacity,
        )

Correctness and complexity

For each trip [passengers, pickup, dropoff], the algorithm adds passengers at pickup and subtracts the same number at dropoff. The prefix sum at any location therefore includes exactly the passengers who have already been picked up but have not yet been dropped off.

That prefix sum is the car’s occupancy. The algorithm returns False precisely when the occupancy exceeds capacity, so it returns the correct answer.

Let n be the number of trips and U be the largest dropoff location. Building the difference array costs O(n), and scanning it costs O(U). The total time is O(n + U), and the extra space is O(U).

Interview follow-ups

What if location values are too large for a dense array?

Store deltas in a hash map instead of allocating an entry for every route location. For each trip, add passengers at the pickup location and subtract them at the dropoff location. Then sort the locations that actually appear and scan those events in order.

This produces the same running occupancy because locations without events do not change the passenger count. The tradeoff is that sorting the distinct event locations costs O(n log n) time in the worst case, while the extra space stays O(n).

Can this be solved with a heap?

Yes. Sort trips by pickup location and maintain a min-heap of active trips ordered by dropoff location. Before processing a pickup, remove every active trip whose dropoff location is less than or equal to that pickup location and subtract its passengers from the current occupancy. Then add the new trip and check capacity.

This works because the heap exposes the trips that finish earliest, so expired trips can be removed before new passengers enter. The approach costs O(n log n) time and O(n) space. It is useful when the interviewer wants to track active trips explicitly, although the difference-array solution is simpler when route coordinates are small.

How would the design change for online trip requests?

If trips arrive one at a time and the system must immediately accept or reject each request, rebuilding a prefix sum after every request is too expensive.

A segment tree can store occupancy over route intervals. Adding a trip performs a range increment on [pickup, dropoff), and the tree’s root tracks the maximum occupancy anywhere on the route. If that maximum exceeds capacity, reject the trip and roll back the range increment. With fixed coordinates or coordinate compression, each update and check costs O(log U). For arbitrary coordinates arriving over time, a dynamic segment tree can allocate nodes only where needed.

Can the algorithm report where capacity is first exceeded?

Yes. During the prefix-sum scan, return the current route location together with False as soon as the running occupancy exceeds capacity.

The proof and asymptotic complexity stay the same. This small change is useful in production because it explains which part of the route caused the rejection.

What changes if the car can travel in both directions?

The original prefix-sum model depends on every trip sharing the same west-to-east order. If the car can reverse direction, numeric location alone no longer determines when pickups and dropoffs happen.

For a fixed route, the same idea still works by scanning events in route order. If the route itself must be chosen, the problem becomes a scheduling or routing problem: the solution must decide an order of travel before it can validate capacity. That is a substantially different optimization problem, not a small modification to the prefix-sum scan.

Practical takeaway

When requests occupy intervals on an ordered line, record where each interval starts and ends. A prefix sum turns those boundary changes into the exact number of active passengers at every point, making the capacity check both simple and efficient.