#1094

Medium

LeetCode Problem Workspace

Car Pooling

Determine if a car can handle multiple trips without exceeding its capacity using array sorting and event simulation techniques.

array sorting heap priority queue simulation prefix sum

Problem Statement

You are given a vehicle with a fixed seating capacity and a list of trips represented as arrays. Each trip array contains the number of passengers, a pickup location, and a dropoff location. The vehicle only moves east, so trips must be scheduled along this single direction without backtracking. Your task is to determine if the vehicle can complete all trips without exceeding its seating limit at any time.

Each trip is represented as trips[i] = [numPassengersi, fromi, toi], where numPassengersi is the number of passengers, fromi is the pickup kilometer mark, and toi is the dropoff kilometer mark. Return true if all trips can be successfully completed under the car's capacity, otherwise return false. Locations are integers representing kilometers due east from the starting point, and all trips must be simulated in order to ensure capacity constraints are not violated.

Examples

Example 1

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

Output: false

Example details omitted.

Example 2

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

Output: true

Example details omitted.

Constraints

1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersi <= 100
0 <= fromi < toi <= 1000
1 <= capacity <= 105

Solution Approach

Transform trips into events

Convert each trip into two events: a pickup increasing passenger count and a dropoff decreasing it. Represent each as [location, changeInPassengers]. This allows us to manage capacity changes as discrete events rather than iterating over each kilometer.

Sort events by location

Sort all pickup and dropoff events by their location in ascending order. If multiple events occur at the same location, process dropoffs before pickups. Sorting ensures we handle capacity changes in the correct eastward sequence, directly aligning with the array plus sorting pattern.

Simulate passenger count and check capacity

Initialize a counter at zero and iterate through the sorted events, updating the counter with each change. If at any point the passenger count exceeds the car's capacity, return false. Otherwise, if all events are processed without exceeding capacity, return true. This step directly connects to the failure mode of exceeding capacity during sequential trip simulation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting events and O(n) for simulating the passenger count, giving O(n log n) overall. Space complexity is O(n) to store all pickup and dropoff events, where n is the number of trips times two.

What Interviewers Usually Probe

Are you tracking passenger changes efficiently rather than simulating each kilometer?
Did you consider edge cases where pickups and dropoffs occur at the same location?
Can you explain why sorting events is necessary for correct simulation?

Common Pitfalls or Variants

Common pitfalls

Processing pickups before dropoffs at the same location can temporarily exceed capacity incorrectly.
Iterating over every kilometer instead of events can lead to unnecessary O(k*n) complexity where k is the max location.
Not handling empty trips or zero passengers may cause index or counter errors.

Follow-up variants

Trips with large ranges but sparse events can use a prefix sum array instead of event simulation.
If all trips have the same pickup or dropoff points, optimize by aggregating changes at each location.
Dynamic capacity changes, such as variable car sizes, can be handled by extending the event simulation with additional state tracking.

FAQ

What is the best approach to solve Car Pooling?

Transform trips into pickup and dropoff events, sort them by location, then simulate passenger counts to ensure capacity is never exceeded.

Why do we need to sort pickup and dropoff events?

Sorting ensures events are processed eastward in the correct sequence, preventing temporary capacity violations and matching the array plus sorting pattern.

Can prefix sum optimize this solution?

Yes, for large but sparse trips, a prefix sum over locations allows constant-time updates and reduces iteration, though the event approach is generally cleaner.

How do I handle multiple events at the same location?

Always process dropoffs before pickups at the same location to avoid incorrectly exceeding car capacity during simulation.

What common mistakes occur when simulating Car Pooling?

Mistakes include simulating each kilometer instead of using events, misordering pickups and dropoffs, and neglecting zero-passenger or empty trip cases.

terminal

Solution

Solution 1: Difference Array

We can use the idea of a difference array, adding the number of passengers to the starting point of each trip and subtracting from the end point. Finally, we just need to check whether the prefix sum of the difference array does not exceed the maximum passenger capacity of the car.

1

2

3

4

5

6

7

8

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))

Continue Practicing

#1738 find kth largest xor coordinate value #1878 get biggest three rhombus sums in a grid #1054 distant barcodes