1094. Car Pooling — DSA Atlas

1094

MediumPrefix Sum and Difference ArrayDifference array with running sweepDifference array over positions

Car Pooling

A car with a fixed capacity drives east and cannot turn around. Given trips where each trip is [numPassengers, from, to], meaning numPassengers board at location from and leave at location to, return true if it is possible to complete all trips without the number of passengers on board ever exceeding capacity, and false otherwise.

Open official problem prompt ↗

In plain English

Decide whether the passenger load ever exceeds capacity at any point along the one-way route.

Picture it like this

Like tracking people in a room with a clicker at the door: +1 when someone enters, -1 when they leave. The running clicker value is the crowd size at any moment, and you never recount everyone already inside.

Example

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Why: Between locations 3 and 5 both groups overlap: 2 + 3 = 5 passengers, which exceeds capacity 4

Constraints

1 <= trips.length <= 10001 <= numPassengers_i <= 1000 <= from_i < to_i <= 10001 <= capacity <= 10^5

Pattern lesson

See the pattern, then code

Difference array over positions

↗

Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. Instead of updating every location in each trip's range, record a +num at the boarding point and a -num at the drop-off point. A running sum over positions then reconstructs the passenger count everywhere in one pass.

New words, made simpleKnow these before the algorithm

Difference array: An array where diff[i] stores the change at position i; its running sum reconstructs the actual value at each position.
Sweep: A single left-to-right accumulation that turns endpoint markers back into per-position totals.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Update every location per trip

Re-touching every location in every range is wasteful when only endpoints matter.

For each trip, add num to every location from from to to, then scan for an overflow.

Time O(n * M)Space O(M)

Best choiceDifference array plus sweep

Each trip is two O(1) updates; a single sweep checks feasibility.

Mark +num and -num at the two endpoints, then sweep once to recover loads.

Time O(n + M)Space O(M)

The rule we keep true

Invariant

After processing all trips, the running sum of diff up to any location equals the exact number of passengers on board at that location.

Why this is correct

Reasoning

Boarding contributes +num from the start location onward and drop-off contributes -num from the end location onward; because a passenger leaves exactly at to, the +num and -num cancel for all locations at or past to, so the prefix sum equals the live passenger count everywhere.

The algorithm in three movesSay these aloud before coding

1Create a diff array over locations 0..1000 initialized to zero

diff[1]+=2, diff[5]-=2

2For each trip add num at from and subtract num at to

diff[3]+=3, diff[7]-=3

3Sweep locations left to right accumulating a running passenger count

cur@1=2, @3=5 > 4 => false

4If the running count ever exceeds capacity return false; otherwise return true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

+2@10

+3@31

-2@52

-3@73

1 · Read[2,1,5]

2 · AskWhere to add and subtract?

3 · Update statediff[1]+=2, diff[5]-=2

4 · ResultEndpoints recorded

Key takeaway

Difference markers; the running sweep hits 5 passengers at location 3, exceeding capacity 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-6Build the difference array
Each trip becomes exactly two updates: board at start, alight at end.
2
Lines 7-11Sweep and check
Accumulate the running load and bail out the moment it exceeds capacity.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Passengers drop off exactly where others board; the drop-off applies at to so loads do not double count
A single trip that alone exceeds capacity returns false
Trips that never overlap keep the running count low and return true

Common beginner mistakes

Marking the drop-off at to+1 instead of to; passengers leave at to, so the -num belongs at index to
Sizing the diff array too small; locations can reach 1000, so it needs 1001 slots
Adding to every intermediate location instead of just the two endpoints, losing the difference-array speedup

Check your understanding

Why is the passenger decrease placed at index to rather than to + 1?

Car Pooling

Car Pooling

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Prefix Sum and Difference Array