LeetCode 1094 - Car Pooling

LeetCode Problem 1094

Difficulty: 🟡 Medium
Topics: Array, Sorting, Heap (Priority Queue), Simulation, Prefix Sum

Solution

Problem Understanding

This problem asks us to determine whether a car can successfully complete a series of passenger trips without ever exceeding its seating capacity.

Each trip is represented as:

[numPassengers, from, to]

This means:

• numPassengers passengers enter the car at location from
• Those same passengers leave the car at location to

The important detail is that the car only moves east. Since the vehicle never turns around, we can process all passenger events in order of location. At every pickup point, passengers enter the car, and at every drop-off point, passengers leave.

The goal is to return true if the car can complete all trips while never exceeding capacity, otherwise return false.

For example:

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

At kilometer 1, two passengers enter.

At kilometer 3, three more passengers enter.

Now there are 5 passengers in the car, which exceeds the capacity of 4, so the answer is false.

The constraints tell us several important things:

• There can be up to 1000 trips.
• Locations range from 0 to 1000.
• Passenger counts are relatively small.
• Capacity can be as large as 100000.

Since the location range is bounded (0 <= from < to <= 1000), we can take advantage of this fact and simulate passenger changes efficiently instead of checking every trip against every other trip.

Several edge cases are important:

• Multiple pickups and drop-offs occurring at the same location.
• Trips that end exactly where another begins.
• Capacity being reached exactly, which is valid.
• Large overlaps where many trips are active simultaneously.
• Minimal inputs, such as only one trip.

The problem guarantees valid trip ranges (from < to), so we never need to handle invalid intervals.

Approaches

Brute Force Approach

A straightforward solution is to simulate every kilometer traveled and track how many passengers are currently in the car.

We can create an array representing locations from 0 to 1000. For every trip:

1. Add passengers to every position between from and to - 1.
2. Check if capacity is exceeded at any point.

For example:

[2,1,5]

Would increase passenger count at:

1, 2, 3, 4

This approach works because it explicitly models the number of passengers at every segment of the journey. However, it performs repeated updates across intervals, making it less efficient than necessary.

Key Insight

We do not need to track every kilometer individually for every trip.

Instead, we only care about where passenger counts change.

At a pickup location:

+numPassengers

At a drop-off location:

-numPassengers

This is a classic prefix sum or difference array observation.

Rather than updating every position in a range, we mark only the beginning and end of the change.

For a trip:

[numPassengers, from, to]

We do:

changes[from] += numPassengers
changes[to] -= numPassengers

Then, by scanning locations from left to right and maintaining a running sum, we always know how many passengers are currently in the car.

If the running sum ever exceeds capacity, we immediately return false.

This is efficient because the location range is small and bounded.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(m)	Updates every kilometer for every trip, where m = 1001 locations
Optimal	O(n + m)	O(m)	Uses a difference array and prefix sum

Here:

• n = number of trips
• m = maximum location (1001)

Algorithm Walkthrough

1. Create a difference array to represent passenger changes at each location.

Since locations are bounded by 1000, create an array of size 1001 + 1 to safely handle drop-offs at position 1000. 2. Process every trip and record passenger changes.

For each trip:

• Add passengers at the pickup point.
• Remove passengers at the drop-off point.

In code terms:

changes[from] += passengers
changes[to] -= passengers

This avoids updating every intermediate kilometer. 3. Traverse locations from west to east.

Maintain a running passenger count.

At each location:

currentPassengers += changes[location]

This tells us exactly how many passengers are in the car at that point. 4. Check capacity immediately.

If:

currentPassengers > capacity

return false.

There is no need to continue because the trip arrangement is impossible. 5. Finish scanning all locations.

If capacity is never exceeded, return true.

Why it works

The algorithm works because the difference array correctly records every passenger entering and leaving the car. When we compute the prefix sum, the running total at any location equals the exact number of passengers currently riding. Since every capacity violation would appear in this running total, checking it at every location guarantees correctness.

Python Solution

from typing import List

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        max_location = 1000
        passenger_changes = [0] * (max_location + 1)

        for passengers, start, end in trips:
            passenger_changes[start] += passengers
            passenger_changes[end] -= passengers

        current_passengers = 0

        for change in passenger_changes:
            current_passengers += change

            if current_passengers > capacity:
                return False

        return True

The implementation begins by creating a fixed-size difference array called passenger_changes. Since the maximum location is 1000, we allocate an array large enough to represent every kilometer.

For each trip, we record only the changes in passenger count. At the pickup location, passengers are added. At the drop-off location, passengers are removed. This transforms interval updates into constant-time operations.

After all trips are processed, we iterate through the locations in increasing order. The variable current_passengers acts as a prefix sum and represents how many passengers are currently in the car.

If the passenger count exceeds capacity at any point, the function immediately returns False. Otherwise, after scanning all locations, the function returns True.

Go Solution

func carPooling(trips [][]int, capacity int) bool {
	maxLocation := 1000
	passengerChanges := make([]int, maxLocation+1)

	for _, trip := range trips {
		passengers := trip[0]
		start := trip[1]
		end := trip[2]

		passengerChanges[start] += passengers
		passengerChanges[end] -= passengers
	}

	currentPassengers := 0

	for _, change := range passengerChanges {
		currentPassengers += change

		if currentPassengers > capacity {
			return false
		}
	}

	return true
}

The Go implementation follows the same logic as the Python version. A slice is used for the difference array, and integer arithmetic is safe because the constraints are far below Go's integer limits.

Unlike Python, Go requires explicit extraction of trip values from slices. Otherwise, the logic remains identical.

No special handling for nil versus empty slices is needed because the constraints guarantee at least one trip.

Worked Examples

Example 1

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

After processing trips:

Location	Passenger Change
1	+2
3	+3
5	-2
7	-3

Now compute the running total.

Location	Change	Current Passengers	Capacity Exceeded?
0	0	0	No
1	+2	2	No
2	0	2	No
3	+3	5	Yes

At location 3, there are 5 passengers, exceeding capacity 4.

Result:

false

Example 2

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

The passenger changes are identical.

Location	Change	Current Passengers	Capacity Exceeded?
0	0	0	No
1	+2	2	No
2	0	2	No
3	+3	5	No
4	0	5	No
5	-2	3	No
6	0	3	No
7	-3	0	No

Capacity is never exceeded.

Result:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	We process each trip once and scan locations once
Space	O(m)	The difference array stores passenger changes for every location

Here, n is the number of trips and m = 1001, the maximum possible location range.

Since m is fixed and small, the algorithm is effectively linear in the number of trips.

Test Cases

solution = Solution()

assert solution.carPooling([[2, 1, 5], [3, 3, 7]], 4) is False
# overlapping trips exceed capacity

assert solution.carPooling([[2, 1, 5], [3, 3, 7]], 5) is True
# overlapping trips exactly fit capacity

assert solution.carPooling([[3, 2, 7]], 3) is True
# single trip exactly equals capacity

assert solution.carPooling([[3, 2, 7]], 2) is False
# single trip exceeds capacity

assert solution.carPooling([[2, 1, 5], [3, 5, 7]], 3) is True
# drop-off and pickup at same location

assert solution.carPooling([[2, 0, 1000]], 2) is True
# maximum trip range

assert solution.carPooling([[2, 0, 1000]], 1) is False
# maximum trip exceeds capacity

assert solution.carPooling(
    [[2, 1, 5], [2, 2, 6], [2, 3, 7]],
    5
) is False
# multiple overlapping trips exceed capacity

assert solution.carPooling(
    [[2, 1, 5], [2, 2, 6], [1, 3, 7]],
    5
) is True
# multiple overlaps exactly meet capacity

assert solution.carPooling(
    [[1, 0, 1], [1, 1, 2], [1, 2, 3]],
    1
) is True
# sequential non-overlapping trips

Test	Why
[[2,1,5],[3,3,7]], 4	Validates overlapping trips exceeding capacity
[[2,1,5],[3,3,7]], 5	Validates exact capacity boundary
[[3,2,7]], 3	Tests single-trip success
[[3,2,7]], 2	Tests single-trip failure
[[2,1,5],[3,5,7]], 3	Validates simultaneous drop-off and pickup
[[2,0,1000]], 2	Tests maximum location range
[[2,0,1000]], 1	Tests failure on maximum range
Multiple overlapping trips	Validates cumulative passenger tracking
Exact capacity overlap	Ensures equality does not fail
Sequential trips	Confirms no false overlap detection

Edge Cases

One important edge case is when passengers are dropped off at the exact location where new passengers are picked up. A buggy implementation might process pickups before drop-offs and temporarily exceed capacity incorrectly. The difference array naturally handles this because both changes occur at the same index and are combined correctly before evaluating capacity.

Another edge case occurs when the passenger count exactly equals the car's capacity. Since the condition is only invalid when the count becomes strictly greater than capacity, the implementation correctly allows equality.

A third important case is highly overlapping trips. For example, many trips may overlap over the same interval and gradually increase the passenger count. A naive implementation could become inefficient or error-prone when repeatedly updating intervals. The difference-array approach correctly aggregates all changes and efficiently computes the total using a prefix sum.

Finally, trips covering the maximum range, such as from 0 to 1000, can cause off-by-one bugs. The implementation safely handles this by allocating enough space for index 1000 and treating the drop-off position correctly.