1094. Car Pooling - Explanation

Description

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 a integer array trips where trips[i] = [numPassengers[i], from[i], to[i]] indicates that the ith trip has numPassengers[i] passengers and the locations to pick them up and drop them off are from[i] and to[i] respectively. The locations are given as the number of kilometers due east from the car's initial location.

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 = [[4,1,2],[3,2,4]], capacity = 4

Output: true

Example 2:

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

Output: false

Constraints:

1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengers[i] <= 100
0 <= from[i] < to[i] <= 1000
1 <= capacity <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

At each pickup location, we need to know how many passengers are currently in the car. We can sort trips by their start location and for each trip, check all previous trips that have not yet dropped off their passengers. If the total exceeds capacity at any point, carpooling is not possible.

Algorithm

Sort all trips by their pickup location (start time).
For each trip at index i:
- Start with the number of passengers from the current trip.
- Check all previous trips (j < i) and add their passengers if their drop-off location is after the current pickup location.
- If the total passengers exceed capacity, return false.
If all trips pass the capacity check, return true.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda x: x[1])

        for i in range(len(trips)):
            curPass = trips[i][0]
            for j in range(i):
                if trips[j][2] > trips[i][1]:
                    curPass += trips[j][0]
            if curPass > capacity:
                return False

        return True

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Min-Heap

Intuition

When we process trips in order of pickup time, we only care about trips whose passengers are still in the car. A min-heap ordered by drop-off time lets us efficiently remove all trips whose passengers have already been dropped off before the current pickup. This way, we maintain a running count of current passengers.

Algorithm

Sort trips by their pickup location.
Use a min-heap to track active trips, ordered by their drop-off location.
For each trip:
- Pop all trips from the heap whose drop-off location is at or before the current pickup, subtracting their passengers from the count.
- Add the current trip's passengers to the count.
- If the count exceeds capacity, return false.
- Push the current trip (drop-off time, passenger count) onto the heap.
Return true if all trips are processed without exceeding capacity.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda t: t[1])

        minHeap = []  # pair of [end, numPassengers]
        curPass = 0

        for numPass, start, end in trips:
            while minHeap and minHeap[0][0] <= start:
                curPass -= heapq.heappop(minHeap)[1]

            curPass += numPass
            if curPass > capacity:
                return False

            heapq.heappush(minHeap, [end, numPass])

        return True

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Line Sweep - I

Intuition

Think of each trip as two events: passengers getting on at the start and passengers getting off at the end. By treating pickups as positive changes and drop-offs as negative changes, we can process all events in sorted order. At any point, if the cumulative passenger count exceeds capacity, the answer is false.

Algorithm

Create a list of events: (location, +passengers) for pickups and (location, -passengers) for drop-offs.
Sort events by location. If two events have the same location, process drop-offs (negative) before pickups to handle edge cases correctly.
Iterate through events, maintaining a running passenger count.
If the count ever exceeds capacity, return false.
Return true after processing all events.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        points = []
        for passengers, start, end in trips:
            points.append([start, passengers])
            points.append([end, -passengers])

        points.sort()
        curPass = 0
        for point, passengers in points:
            curPass += passengers
            if curPass > capacity:
                return False

        return True

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Line Sweep - II

Intuition

Instead of sorting events, we can use an array where each index represents a location on the route. We record passenger changes at each location: add passengers at pickup points and subtract at drop-off points. A single pass through this array gives us the passenger count at each location.

Algorithm

Find the range of locations (leftmost pickup to rightmost drop-off).
Create an array of size (range + 1) initialized to zero.
For each trip, add passengers at the pickup index and subtract at the drop-off index.
Iterate through the array, accumulating the passenger count.
If the count ever exceeds capacity, return false. Otherwise, return true.

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        L, R = float("inf"), float("-inf")
        for _, start, end in trips:
            L = min(L, start)
            R = max(R, end)

        N = R - L + 1
        passChange = [0] * (N + 1)
        for passengers, start, end in trips:
            passChange[start - L] += passengers
            passChange[end - L] -= passengers

        curPass = 0
        for change in passChange:
            curPass += change
            if curPass > capacity:
                return False

        return True

Time & Space Complexity

Time complexity: $O(n + N)$
Space complexity: $O(N)$

Where $n$ is the size of the array $trips$ and $N$ is the difference between the rightmost location and the leftmost location.

Common Pitfalls

Not Processing Drop-offs Before Pickups at Same Location

When a passenger is dropped off and another is picked up at the same location, the drop-off must happen first. Failing to sort events so that drop-offs (negative values) come before pickups at the same location causes false capacity violations.

# Wrong: no tiebreaker for same location
points.sort(key=lambda x: x[0])
# Correct: drop-offs (negative) before pickups at same location
points.sort(key=lambda x: (x[0], x[1]))

Checking Passengers Still in Car at Drop-off Location

Passengers are dropped off at the end location and are not in the car during that location. A common mistake is including passengers who should have already exited, leading to overcounting.

# Wrong: includes passengers still at drop-off
if trips[j][2] >= trips[i][1]:
# Correct: only count if drop-off is strictly after pickup
if trips[j][2] > trips[i][1]:

Off-by-One Error in Difference Array Index

When using a difference array, failing to account for the offset between actual locations and array indices causes incorrect passenger counts. This is especially problematic when locations do not start at zero.

# Wrong: assumes locations start at 0
passChange[start] += passengers
passChange[end] -= passengers
# Correct: adjust for minimum location offset
passChange[start - L] += passengers
passChange[end - L] -= passengers