Domain 2MediumMEDIUM

Car Pooling

LeetCode problem 1094: Car Pooling (medium).

Domain: medium•Updated: 2026-09-08
#Greedy

Problem Breakdown

We are tasked with determining if a vehicle can complete a series of trips without exceeding its capacity at any point during the journey. The car moves strictly East, meaning locations increase monotonically from 0 upwards. Each trip specifies how many passengers get on (num_passengers) and off (at end_location).

Inputs:

  • trips: A list of lists where each inner list is [passengers, start_loc, end_loc].
  • capacity: An integer representing the maximum number of seats.

Output:

  • Boolean (True if all trips can be accommodated, False otherwise).

Implicit Constraints & Edge Cases:

  1. Coordinate Range: Locations are integers up to 1000. This suggests a coordinate-based approach (difference array) is viable and efficient compared to sorting events for larger ranges.
  2. Simultaneous Events: A passenger drops off at end_loc while another picks up at the same location. Since they occupy seats on different intervals, we must ensure that capacity isn’t exceeded between these points or during the transition. The standard interpretation is that drop-offs happen before pickups effectively (or net change logic handles it), so processing changes at a specific coordinate index correctly reflects load for subsequent distance.
  3. Empty Input: If trips is empty, no passengers are needed; capacity constraint is trivially satisfied (True).

Intuition

A brute-force simulation would involve iterating through every kilometer from the minimum start location to the maximum end location (up to 1000). At each step, we’d check which trips are active. This results in O(N⋅M)O(N \cdot M) complexity where NN is trip count and MM is max distance. While acceptable for small constraints (M=1000M=1000), it’s inefficient logic-wise because the state only changes at specific event points (start/end locations).

Key Insight: The passenger load on the vehicle only changes when a pickup or drop-off occurs. This transforms the problem into an interval scheduling / sweep-line problem. We can track “net change” in passengers for each location using a difference array. By iterating through these events, we maintain a running sum of current passengers and check against capacity.

Approach

  1. Initialize Tracking Structure: Create a list (difference array) large enough to cover the maximum end location found in any trip plus one buffer. Initialize with zeros. Given constraints (max_loc≤1000max\_loc \le 1000), an array of size ~1005 is sufficient and efficient.
  2. Record Changes: Iterate through each trip. For a trip [num, start, end]:
    • Add num to the index corresponding to start. This represents passengers entering at this location.
    • Subtract num from the index corresponding to end. This represents passengers leaving (freeing capacity) exactly when they reach their destination. Note: We subtract at end, not end - 1, because once a passenger reaches end, they are no longer occupying seats for any distance beyond that point.
  3. Sweep Line Check: Iterate through the difference array from index 0 up to the maximum location encountered (or simply iterate over all populated indices). Maintain a running sum (current_passengers).
  4. Capacity Validation: At each step, add the change recorded at that location to current_passengers. If current_passengers exceeds capacity, return False immediately.
  5. Completion: If we finish iterating through all locations without exceeding capacity, return True.

Complexity Analysis

  • Time Complexity: O(T+M)O(T + M) where TT is the number of trips and MM is the maximum location value (bounded by 1000). We iterate once to populate changes (O(T)O(T)) and once through the array range (O(M)O(M)). Given constraints, this effectively behaves as linear time relative to input size.
  • Space Complexity: O(M)O(M) for the difference array where MM is the maximum location value (1002 in worst case per constraints). This fits easily within memory limits.

Solution

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # Determine max end location to size our difference array correctly.
        # Constraints say locations <= 1000, but dynamic sizing is safer practice.
        if not trips:
            return True
            
        max_end = 0
        for _, start, end in trips:
            max_end = max(max_end, end)
            
        # Difference array to track passenger changes at each location.
        # Size needs to be max_end + 1 because we access index 'end'.
        diff_array = [0] * (max_end + 2) 
        
        for num_passengers, start_loc, end_loc in trips:
            diff_array[start_loc] += num_passengers
            diff_array[end_loc] -= num_passengers
            
        current_load = 0
        
        # Sweep through locations. 
        # We iterate up to max_end because that's the furthest point we need to track load for.
        # Note: Iterating beyond max_end is unnecessary as no trips end there, but safe to go higher if needed.
        for i in range(max_end + 1):
            current_load += diff_array[i]
            
            # If at any location the running sum exceeds capacity, it's impossible.
            if current_load > capacity:
                return False
                
        return True

Edge Cases Handled

  • Empty Trips: The loop over trips won’t execute; logic implicitly returns True. Added explicit check for clarity in thought process (though code handles it naturally).
  • Capacity Exactly Met: If load equals capacity, the condition current_load > capacity is false, so we continue. This correctly allows full utilization of seats.
  • Drop-off at Same Location as Pick-up: The difference array logic processes both increments and decrements at index i. Since Python evaluates sequentially in a loop, if multiple events happen at same location (e.g., drop off then pick up), the net change is applied to current_load before checking capacity. This correctly models that passengers leaving free space for those entering simultaneously without violating constraints between intervals.
  • Large Capacity: Python handles large integers automatically; no overflow issues compared to languages like C++ or Java.