How do you solve Car Pooling?

Create an array representing all possible stops (0 to 1000). For each trip, add the number of passengers at the start index and subtract at the end index. Then, iterate through the array accumulating passenger counts. If at any point the accumulated count exceeds capacity, return false. Otherwise, return true after the iteration.

What pattern does Car Pooling use?

The Pattern: Prefix Sum (Difference Array) The Heuristic: When a problem involves multiple range updates and queries on a linear structure, use a difference array to record incremental changes at boundaries, then compute prefix sums to efficiently reconstruct the full state.

Car Pooling — Prefix Sum

Q: What is the time complexity of Car Pooling?

O(n + d). Processing each trip to update the difference array takes O(n), and iterating through the stops array of fixed size (1001) takes O(d), resulting in O(n + d) time complexity.

Problem

Given an array trips where trips[i] = [numPassengers, startLocation, endLocation] and an integer capacity, return true if it is possible to pick up and drop off all passengers for all the given trips without exceeding the vehicle capacity at any point, otherwise return false.

1 ≤ trips.length ≤ 1000
trips[i].length == 3
1 ≤ numPassengers ≤ 100
0 ≤ startLocation < endLocation ≤ 1000
1 ≤ capacity ≤ 10⁵

Example

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

Output: false

The vehicle picks up 2 passengers at location 1 and drops them off at location 5. It also picks up 3 passengers at location 3 and drops them off at location 7. Between locations 3 and 5, the vehicle carries 5 passengers, exceeding the capacity of 4, so the output is false.

Approach

Straightforward Solution

A naive approach simulates the vehicle's journey step-by-step, updating the passenger count at every location between start and end for each trip. This approach is O(n * d), where d is the distance range, which is inefficient for large inputs.

Core Observation

The number of passengers changes only at discrete locations where passengers are picked up or dropped off. Tracking the net change in passengers at each location allows efficient computation of the current load at any point.

Path to Optimal

Preview

Recognizing that passenger changes occur only at trip start and end points, the problem can be transformed into a difference array or prefix sum problem…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Create an array representing all possible stops (0 to 1000). For each trip, add the number of passengers at the start index and subtract at the end index…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + d)

Processing each trip to update the difference array takes O(n), and iterating through the stops array of fixed size (1001) takes O(d), resulting in O(n + d) time complexity.

Space

O(d)

The auxiliary space is O(d) for the stops array, where d is the maximum location index (1001). This space is necessary to track passenger changes at each stop.

Solution

Python

1class Solution:
  def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
      stops = [0] * 1001
4
      for num, start, end in trips:
          stops[start] += num
          stops[end] -= num
8
      curr = 0
      for x in stops:
          curr += x
          if curr > capacity:
              return False
14
      return True

Step-by-Step Solution

1

Record Passenger Pickups and Drop-offs at Each Location

3stops = [0] * 1001
5for num, start, end in trips:
6    stops[start] += num
7    stops[end] -= num

Objective

To build a difference array that captures net passenger changes at each stop based on trip data.

Key Insight

By incrementing the passenger count at the start location and decrementing at the end location for each trip, the difference array compactly encodes all passenger changes. This approach avoids simulating every location between start and end, enabling efficient aggregation later.

Interview Quick-Check

Core Logic

Incrementing at start and decrementing at end for each trip encodes passenger changes as a difference array, enabling O(1) updates per trip.

Common Pitfalls & Bugs

Forgetting to decrement at the end location leads to incorrect passenger counts, as passengers must be considered dropped off exactly at that point.

2

Accumulate Passenger Counts and Validate Capacity Constraints

To compute the running total of passengers at each stop and check if capacity is exceeded.

3

Confirm Feasibility After Processing All Stops

To return true if the vehicle never exceeds capacity throughout the trip.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 12 Critical

if curr > capacity:

Check if the current passenger count exceeds vehicle capacity.

This conditional detects overloads immediately, enabling early termination to improve efficiency and correctness.

Line 6 Critical

stops[start] += num

Add the number of passengers picked up at the start location.

Incrementing at the start index records the addition of passengers boarding the vehicle, marking the beginning of their journey.

Line 7 Critical

stops[end] -= num

Subtract the number of passengers dropped off at the end location.

Decrementing at the end index records passengers leaving the vehicle, ensuring the difference array accurately reflects net passenger changes.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does using a difference array with prefix sums allow efficient tracking of passenger counts instead of simulating every location for each trip?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Car Pooling from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Car Pooling drill

or drill a free problem

1	`class Solution:`
2	`def carPooling(self, trips: List[List[int]], capacity: int) -> bool:`
3	`stops = [0] * 1001`
4
5	`for num, start, end in trips:`
6	`stops[start] += num`
7	`stops[end] -= num`
8
9	`curr = 0`
10	`for x in stops:`
11	`curr += x`
12	`if curr > capacity:`
13	`return False`
14
15	`return True`

3	`stops = [0] * 1001`
5	`for num, start, end in trips:`
6	`stops[start] += num`
7	`stops[end] -= num`