Car Pooling

Difficulty: Medium Source: NeetCode

Problem

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengers_i, from_i, to_i] indicates that the ith trip has numPassengers_i passengers and the passengers must be picked up from from_i and dropped off at to_i.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

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

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

Constraints:

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengers_i <= 100
• 0 <= from_i < to_i <= 1000
• 1 <= capacity <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Difference arrays — a technique for efficiently applying range updates and querying a prefix sum
• Min-heap — processing events (drop-offs) in order of time
• Sorting — processing trips in order of pickup time

1. Difference Array

Intuition

Since all locations are between 0 and 1000, we can model passenger counts over position with a difference array. For each trip, add numPassengers at from and subtract at to. Then compute the prefix sum to get the occupancy at each position. If any position exceeds capacity, return false.

Algorithm

1. Create a difference array diff[0..1001] initialized to 0.
2. For each trip [num, frm, to]: diff[frm] += num, diff[to] -= num.
3. Compute the running sum (prefix sum) of diff. If any prefix sum > capacity, return false.
4. Return true.

Solution

def carPooling(trips, capacity):
    diff = [0] * 1001  # locations are in [0, 1000]

    for num, frm, to in trips:
        diff[frm] += num
        diff[to] -= num  # passengers leave at 'to'

    current = 0
    for count in diff:
        current += count
        if current > capacity:
            return False

    return True


print(carPooling([[2,1,5],[3,3,7]], 4))   # False
print(carPooling([[2,1,5],[3,3,7]], 5))   # True
print(carPooling([[3,2,7],[3,7,9],[8,3,9]], 11))  # True

Complexity

• Time: O(n + L) where n = number of trips and L = 1001 (location range)
• Space: O(L)

2. Min-Heap — Event Processing

Intuition

Sort trips by pickup location. Process trips in order: whenever we pick up passengers, also drop off any passengers whose destination we’ve already passed. Use a min-heap ordered by drop-off location to efficiently find who should exit next.

Algorithm

1. Sort trips by from location.
2. Initialize heap (min by to location) and current_passengers = 0.
3. For each trip [num, frm, to]: a. Drop off all passengers with to <= frm (pop from heap while condition holds, subtract from current). b. Add num to current passengers and push (to, num) onto the heap. c. If current_passengers > capacity, return false.
4. Return true.

Solution

import heapq

def carPooling(trips, capacity):
    # Sort by pickup location
    trips = sorted(trips, key=lambda x: x[1])

    heap = []  # (dropoff_location, num_passengers)
    current = 0

    for num, frm, to in trips:
        # Drop off passengers who have reached their destination
        while heap and heap[0][0] <= frm:
            _, dropped = heapq.heappop(heap)
            current -= dropped

        # Pick up new passengers
        current += num
        heapq.heappush(heap, (to, num))

        if current > capacity:
            return False

    return True


print(carPooling([[2,1,5],[3,3,7]], 4))            # False
print(carPooling([[2,1,5],[3,3,7]], 5))            # True
print(carPooling([[3,2,7],[3,7,9],[8,3,9]], 11))   # True
print(carPooling([[9,3,4],[9,1,7],[4,2,4]], 13))   # True

Complexity

• Time: O(n log n) — sorting + heap operations
• Space: O(n)

Common Pitfalls

Passengers exit at to, not at to - 1. When a trip is [num, 3, 7], passengers leave at position 7. At position 7, those seats are free again. The difference array subtract should be at index to, not to - 1.

Heap approach: drop off before picking up. When we arrive at location frm, we should first drop off any passengers with dropoff <= frm before counting the new pickups. If you pick up first and then drop off, you’ll get a false overcount.

Not handling multiple trips with the same pickup location. The heap approach handles this naturally because we sort by from, and multiple trips at the same from are all processed before the capacity check.