LeetCode 1094: Car Pooling

Problem Restatement

We have a car with capacity seats.

We are given a list of trips: each trip [numPassengers, from, to] means numPassengers passengers board at from and alight at to.

We need to return true if it is possible to pick up all passengers without exceeding capacity at any point.

The official constraints state that 1 <= trips.length <= 1000, 1 <= numPassengers <= 100, and 0 <= from < to <= 1000.

Input and Output

Function shape:

def carPooling(trips: list[list[int]], capacity: int) -> bool:
    ...

Examples

Example 1:

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

At stop 1: 2 board → 2 passengers.

At stop 3: 3 board → 5 passengers. Exceeds capacity 4.

Answer:

False

Example 2:

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

At stop 3: 5 passengers. Exactly at capacity.

Answer:

True

Key Insight

Use a difference array on the stops.

For each trip, add numPassengers at from and subtract numPassengers at to.

Compute the prefix sum and check if it ever exceeds capacity.

Algorithm

1. Create a stops array of size 1001.
2. For each trip, stops[from] += numPassengers and stops[to] -= numPassengers.
3. Compute the running sum. If it exceeds capacity at any point, return False.
4. Return True.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        stops = [0] * 1001

        for num, frm, to in trips:
            stops[frm] += num
            stops[to] -= num

        current = 0
        for passengers in stops:
            current += passengers
            if current > capacity:
                return False

        return True

Testing

def run_tests():
    s = Solution()

    assert s.carPooling([[2,1,5],[3,3,7]], 4) == False
    assert s.carPooling([[2,1,5],[3,3,7]], 5) == True
    assert s.carPooling([[3,2,7],[3,7,9],[8,3,9]], 11) == True
    assert s.carPooling([[2,1,5],[3,5,7]], 3) == True

    print("all tests passed")

run_tests()