AlgoMaster Logo

Car Pooling

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

A car with a fixed number of seats drives east along a straight road. Each trip [numPassengers, from, to] picks up a group at kilometer from and drops it off at kilometer to. The task is to decide whether every trip can be served without the passenger count ever exceeding the capacity.

The drop-off rule matters. When a group is dropped off at location to, it is no longer in the car at that location, so a group leaving at location 5 and a group boarding at location 5 can share the same seats. Each trip occupies the half-open interval [from, to), and every approach below has to respect that boundary.

There is no need to simulate the car kilometer by kilometer. Each trip reduces to two events: passengers get on at from and get off at to. Tracking these events and the running total of passengers at each location answers the question: does the total ever exceed the capacity?

Key Constraints:

  • 1 <= trips.length <= 1000 → With at most 1000 trips, even the O(n * L) brute force over all 1001 locations runs in about a million operations.
  • 0 <= fromi < toi <= 1000 → Locations are bounded by 1000, which makes a fixed-size array indexed by location practical.
  • 1 <= numPassengersi <= 100 → At most 100 passengers per trip across 1000 trips means the running count never exceeds 100,000, well within a 32-bit integer.

Approach 1: Brute Force (Simulate Every Location)

Intuition

For each location from 0 to 1000, count how many passengers are in the car at that point. A trip [numPassengers, from, to] contributes passengers at any location loc where from <= loc < to. If the total at any location exceeds the capacity, return false.

Checking every trip at every location is wasteful, but it is a direct translation of the problem statement, and the comparison from <= loc < to makes the half-open interval rule explicit.

Algorithm

  1. For each location loc from 0 to 1000:
    • Initialize currentPassengers = 0.
    • For each trip [numPassengers, from, to]:
      • If from <= loc < to, add numPassengers to currentPassengers.
    • If currentPassengers > capacity, return false.
  2. If we checked all locations without exceeding capacity, return true.

Visualization and Code

Loading animation...

A trip spanning locations 1 to 5 gets checked at all 1001 locations but contributes passengers at only 4 of them. The next approach records only the locations where the count changes and processes those in sorted order.

Approach 2: Sorting Events

Intuition

Each trip produces two events: passengers board at from and leave at to. Collect all 2n events, sort them by location, and process them in order while maintaining a running count of passengers. If the count ever exceeds the capacity, return false.

When a drop-off and a pick-up happen at the same location, the drop-off must be processed first, because passengers dropped at location to are no longer in the car at that location. Sorting drop-offs (negative changes) before pick-ups (positive changes) at the same location enforces this. The ordering is not optional: with trips [2,1,5] and [3,5,7] and capacity 3, processing the pick-up at location 5 before the drop-off would count 5 passengers and return a wrong false.

Algorithm

  1. Create a list of events. For each trip [numPassengers, from, to]:
    • Add (from, +numPassengers) for the pick-up.
    • Add (to, -numPassengers) for the drop-off.
  2. Sort events by location. For events at the same location, process drop-offs (negative) before pick-ups (positive).
  3. Initialize currentPassengers = 0.
  4. For each event (location, change):
    • Add change to currentPassengers.
    • If currentPassengers > capacity, return false.
  5. Return true.

Visualization and Code

Loading animation...

Sorting costs O(n log n) and works for any coordinate range. Here the locations are bounded by 1000, so an array indexed by location can replace the sort entirely.

Approach 3: Difference Array (Line Sweep)

Intuition

Since locations only go from 0 to 1000, we can use an array of size 1001 where index i represents location i. For each trip, we record the passenger change directly in the array: add passengers at the pick-up location, subtract them at the drop-off location. After processing all trips, we sweep through the array maintaining a running sum. If it ever exceeds capacity, we return false.

This is the difference array technique: each cell stores the net change in passenger count at its location, and the prefix sum reconstructs the actual count.

Algorithm

  1. Create an array delta of size 1001, initialized to zeros.
  2. For each trip [numPassengers, from, to]:
    • Add numPassengers to delta[from] (passengers board).
    • Subtract numPassengers from delta[to] (passengers leave).
  3. Initialize currentPassengers = 0.
  4. For each location i from 0 to 1000:
    • Add delta[i] to currentPassengers.
    • If currentPassengers > capacity, return false.
  5. Return true.

Visualization and Code

Loading animation...