Car Pooling — LeetCode 1094 Python Solution

The problem

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

Example

Input

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

Output

false

Python solution

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        mx = max(e[2] for e in trips)
        d = [0] * (mx + 1)
        for x, f, t in trips:
            d[f] += x
            d[t] -= x
        return all(s <= capacity for s in accumulate(d))

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1094. Car Pooling is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems