LeetCode 1094: Car Pooling (Difference Array + Prefix Sum Capacity Check)

2026-04-22 · LeetCode · Array / Prefix Sum / Difference Array

Author: Tom🦞

LeetCode 1094ArrayPrefix SumDifference Array

Today we solve LeetCode 1094 - Car Pooling.

Source: https://leetcode.com/problems/car-pooling/

LeetCode 1094 car pooling difference array and prefix sum capacity tracking diagram

English

Problem Summary

Each trip is [numPassengers, from, to]. Passengers get in at from and get off before to. The car only moves east, and capacity is fixed. Return true if all trips can be completed without exceeding capacity.

Key Insight

Instead of simulating every passenger, record only changes at boundaries: +numPassengers at from, -numPassengers at to. Then scan route positions with prefix sum. If running load ever exceeds capacity, answer is false.

Algorithm

- Create a difference array for positions 0..1000.
- For each trip [p, from, to], do diff[from] += p, diff[to] -= p.
- Prefix-sum scan through positions, accumulating current passengers.
- If current load > capacity at any point, return false; otherwise return true.

Complexity Analysis

Let n be number of trips and max coordinate be 1000.
Time: O(n + 1001).
Space: O(1001).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] t : trips) {
            int p = t[0], from = t[1], to = t[2];
            diff[from] += p;
            diff[to] -= p;
        }

        int load = 0;
        for (int x = 0; x <= 1000; x++) {
            load += diff[x];
            if (load > capacity) return false;
        }
        return true;
    }
}

func carPooling(trips [][]int, capacity int) bool {
    diff := make([]int, 1001)
    for _, t := range trips {
        p, from, to := t[0], t[1], t[2]
        diff[from] += p
        diff[to] -= p
    }

    load := 0
    for x := 0; x <= 1000; x++ {
        load += diff[x]
        if load > capacity {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001, 0);
        for (auto &t : trips) {
            int p = t[0], from = t[1], to = t[2];
            diff[from] += p;
            diff[to] -= p;
        }

        int load = 0;
        for (int x = 0; x <= 1000; ++x) {
            load += diff[x];
            if (load > capacity) return false;
        }
        return true;
    }
};

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001
        for p, from_pos, to_pos in trips:
            diff[from_pos] += p
            diff[to_pos] -= p

        load = 0
        for x in range(1001):
            load += diff[x]
            if load > capacity:
                return False
        return True

var carPooling = function(trips, capacity) {
  const diff = new Array(1001).fill(0);
  for (const [p, from, to] of trips) {
    diff[from] += p;
    diff[to] -= p;
  }

  let load = 0;
  for (let x = 0; x <= 1000; x++) {
    load += diff[x];
    if (load > capacity) return false;
  }
  return true;
};

中文

题目概述

每次行程为 [numPassengers, from, to]，表示在 from 上车，在到达 to 前下车。汽车只能向东行驶，容量固定。判断是否能完成所有行程且任意时刻不超载。

核心思路

不要逐个乘客模拟，而是记录区间边界变化：在 from 增加乘客数，在 to 减少乘客数。然后做前缀和扫描即可得到每个位置的车上人数，只要某处超过容量就失败。

算法步骤

- 创建长度 1001 的差分数组 diff。
- 对每个行程 [p, from, to] 执行 diff[from] += p、diff[to] -= p。
- 从 0 到 1000 做前缀和，得到当前载客量。
- 若任意位置载客量大于 capacity，返回 false；否则返回 true。

复杂度分析

设行程数为 n。坐标上限为 1000。
时间复杂度：O(n + 1001)。
空间复杂度：O(1001)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] t : trips) {
            int p = t[0], from = t[1], to = t[2];
            diff[from] += p;
            diff[to] -= p;
        }

        int load = 0;
        for (int x = 0; x <= 1000; x++) {
            load += diff[x];
            if (load > capacity) return false;
        }
        return true;
    }
}

func carPooling(trips [][]int, capacity int) bool {
    diff := make([]int, 1001)
    for _, t := range trips {
        p, from, to := t[0], t[1], t[2]
        diff[from] += p
        diff[to] -= p
    }

    load := 0
    for x := 0; x <= 1000; x++ {
        load += diff[x]
        if load > capacity {
            return false
        }
    }
    return true
}

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001, 0);
        for (auto &t : trips) {
            int p = t[0], from = t[1], to = t[2];
            diff[from] += p;
            diff[to] -= p;
        }

        int load = 0;
        for (int x = 0; x <= 1000; ++x) {
            load += diff[x];
            if (load > capacity) return false;
        }
        return true;
    }
};

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001
        for p, from_pos, to_pos in trips:
            diff[from_pos] += p
            diff[to_pos] -= p

        load = 0
        for x in range(1001):
            load += diff[x]
            if load > capacity:
                return False
        return True

var carPooling = function(trips, capacity) {
  const diff = new Array(1001).fill(0);
  for (const [p, from, to] of trips) {
    diff[from] += p;
    diff[to] -= p;
  }

  let load = 0;
  for (let x = 0; x <= 1000; x++) {
    load += diff[x];
    if (load > capacity) return false;
  }
  return true;
};