Problem Description

You have a car that can hold a certain number of passengers (given by capacity) and it can only travel in one direction - east. You cannot turn the car around to go back west.

You're given an array called trips where each trip is represented as [numPassengers, from, to]:

• numPassengers: the number of passengers for this trip
• from: the pickup location (in kilometers east from starting point)
• to: the drop-off location (in kilometers east from starting point)

Your task is to determine if it's possible to complete all the trips without exceeding the car's capacity at any point during the journey. Return true if all trips can be completed successfully, or false if the car would be over capacity at any point.

For example, if your car has a capacity of 4 and you have trips [[2, 1, 5], [3, 3, 7]], this means:

• At kilometer 1, pick up 2 passengers and drop them off at kilometer 5
• At kilometer 3, pick up 3 passengers and drop them off at kilometer 7

The car would have:

• 0 passengers from start to kilometer 1
• 2 passengers from kilometer 1 to 3
• 5 passengers from kilometer 3 to 5 (2 + 3 = 5, which exceeds capacity of 4)

So this would return false.

The solution uses a difference array technique where it tracks passenger changes at each location - adding passengers at pickup points and subtracting at drop-off points. By calculating the running sum (prefix sum) of these changes, we can determine the number of passengers in the car at each point and check if it ever exceeds capacity.

Intuition

Think about the problem from a timeline perspective. As the car moves east, passengers get on and off at different points. At any given location, we need to know how many passengers are in the car to check if we're within capacity.

The key insight is that we only care about the points where something changes - either passengers get on or passengers get off. Between these events, the number of passengers stays the same.

Instead of simulating the entire journey kilometer by kilometer, we can focus on these "event points." At each pickup location, the passenger count increases, and at each drop-off location, it decreases.

This naturally leads us to think about tracking the changes (deltas) at each location:

• When passengers board at location from, we add +numPassengers
• When passengers leave at location to, we add -numPassengers

By recording these changes in an array indexed by location, we create what's called a difference array. The beauty of this approach is that if we calculate the running sum (prefix sum) of this difference array, we get the actual number of passengers in the car at each location.

For example, if we have +2 at location 1 and -2 at location 5, the prefix sum tells us there are 2 passengers from location 1 to 4, and 0 passengers from location 5 onward.

Once we have the passenger count at each point through the prefix sum, we simply check if any point exceeds the car's capacity. If none do, all trips are feasible; otherwise, they're not.

This approach is efficient because we only process the locations where events occur, rather than simulating every single kilometer of the journey.

Learn more about Prefix Sum, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a difference array to efficiently track passenger changes throughout the journey.

Step 1: Find the maximum location

mx = max(e[2] for e in trips)

We first find the farthest drop-off location among all trips. This tells us how large our difference array needs to be.

Step 2: Create the difference array

d = [0] * (mx + 1)

We initialize a difference array d with zeros, where d[i] will store the net change in passengers at location i. The array size is mx + 1 to include all locations from 0 to mx.

Step 3: Record passenger changes

for x, f, t in trips:
    d[f] += x
    d[t] -= x

For each trip with x passengers from location f to location t:

• At the pickup location f, we add x passengers: d[f] += x
• At the drop-off location t, we remove x passengers: d[t] -= x

This records all the "events" - when passengers board and when they leave.

Step 4: Calculate prefix sum and check capacity

return all(s <= capacity for s in accumulate(d))

The accumulate(d) function computes the prefix sum of the difference array. Each value in this prefix sum represents the actual number of passengers in the car at that location.

For example, if d = [0, 2, 0, 3, 0, -2, 0, -3], then accumulate(d) gives us [0, 2, 2, 5, 5, 3, 3, 0], showing the passenger count at each location.

The all() function checks if every passenger count s in the prefix sum is within capacity. If all values are <= capacity, the function returns true; otherwise, it returns false.

This solution has a time complexity of O(n + m) where n is the number of trips and m is the maximum location value, and space complexity of O(m) for the difference array.

Example Walkthrough

Let's walk through a concrete example with capacity = 4 and trips = [[2, 1, 5], [3, 3, 7]].

Step 1: Find the maximum location The drop-off locations are 5 and 7, so mx = 7.

Step 2: Create the difference array We create an array of size 8 (indices 0 to 7):

d = [0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Record passenger changes Process first trip [2, 1, 5]:

• At location 1, 2 passengers board: d[1] += 2
• At location 5, 2 passengers leave: d[5] -= 2

d = [0, 2, 0, 0, 0, -2, 0, 0]

Process second trip [3, 3, 7]:

• At location 3, 3 passengers board: d[3] += 3
• At location 7, 3 passengers leave: d[7] -= 3

d = [0, 2, 0, 3, 0, -2, 0, -3]

Step 4: Calculate prefix sum and check capacity Computing the running sum of the difference array:

• Location 0: sum = 0 (no passengers)
• Location 1: sum = 0 + 2 = 2 (2 passengers board)
• Location 2: sum = 2 + 0 = 2 (no change)
• Location 3: sum = 2 + 3 = 5 (3 more passengers board, total 5)
• Location 4: sum = 5 + 0 = 5 (no change)
• Location 5: sum = 5 + (-2) = 3 (2 passengers leave)
• Location 6: sum = 3 + 0 = 3 (no change)
• Location 7: sum = 3 + (-3) = 0 (3 passengers leave)

The prefix sum is [0, 2, 2, 5, 5, 3, 3, 0], representing the passenger count at each location.

Since we have 5 passengers at locations 3 and 4, which exceeds our capacity of 4, the function returns false.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + M), where n is the number of trips and M is the maximum end point in the trips. Breaking down the operations:

• Finding the maximum end point: O(n) as it iterates through all trips
• Initializing the difference array: O(M) to create an array of size M + 1
• Processing all trips to update the difference array: O(n) as it iterates through each trip once
• Computing the prefix sum using accumulate and checking capacity: O(M) as it processes the difference array

The overall time complexity is O(n + M). Since in this problem M ≤ 1000 is bounded by a constant, the time complexity can be considered O(n) when n is large.

The space complexity is O(M), where M is the maximum end point in the trips. This is due to the difference array d which has a size of M + 1. The accumulate function generates values on-the-fly without creating an additional array, so it doesn't add to the space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error with Array Size

A common mistake is creating the difference array with size max_location instead of max_location + 1. Since we need to access index max_location (the farthest drop-off point), the array must have at least max_location + 1 elements.

Incorrect:

max_location = max(trip[2] for trip in trips)
difference_array = [0] * max_location  # Wrong! Will cause IndexError

Correct:

max_location = max(trip[2] for trip in trips)
difference_array = [0] * (max_location + 1)  # Correct size

2. Misunderstanding When Passengers Leave

Some might think passengers are still in the car at their drop-off location and subtract them after that point. However, passengers leave exactly at their destination, so the subtraction should happen at to_location, not to_location + 1.

Incorrect:

for num_passengers, from_location, to_location in trips:
    difference_array[from_location] += num_passengers
    if to_location + 1 < len(difference_array):
        difference_array[to_location + 1] -= num_passengers  # Wrong timing!

Correct:

for num_passengers, from_location, to_location in trips:
    difference_array[from_location] += num_passengers
    difference_array[to_location] -= num_passengers  # Passengers leave at destination

3. Memory Inefficiency with Sparse Locations

If the locations are very sparse (e.g., trips only at locations 1, 1000, and 100000), creating an array of size 100001 wastes memory. A more efficient approach uses a dictionary or sorts events.

Memory-Efficient Alternative:

def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    events = []
    for num_passengers, from_loc, to_loc in trips:
        events.append((from_loc, num_passengers))   # Pickup event
        events.append((to_loc, -num_passengers))     # Drop-off event
  
    events.sort()  # Sort by location
    current_passengers = 0
  
    for location, passenger_change in events:
        current_passengers += passenger_change
        if current_passengers > capacity:
            return False
  
    return True

4. Empty Trips Edge Case

While rare in this problem, handling empty input gracefully is good practice:

if not trips:
    return True  # No trips means we can complete all trips
  
max_location = max(trip[2] for trip in trips)  # This would fail on empty list