Skip to main content
Talentd

Car Pooling - Solution & Explanation

MediumArraySortingHeap (Priority Queue)Simulation17 min readAsked at: Amazon, Microsoft, Goldman Sachs +9
Practice this problem

Problem Statement

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Approach Overview

Problem Overview: You receive a list of trips where each trip is [numPassengers, start, end]. A car drives east and cannot turn around. At each location, passengers may get in or out. The goal is to determine whether the car's passenger count ever exceeds its capacity during the journey.

Approach 1: Simulate Passenger Count with Difference Array (Prefix Sum) (Time: O(n + m), Space: O(m))

This approach treats the road as a timeline of passenger changes. For each trip, increment the passenger count at start and decrement it at end. Store these changes in a difference array where each index represents a location. After processing all trips, run a prefix sum across the array to reconstruct the actual passenger count at every point.

The key insight: instead of simulating each trip step‑by‑step, record only where passenger counts change. The prefix sum accumulates those changes efficiently. If the running total ever exceeds capacity, the schedule is impossible. This technique is common in prefix sum and range update problems and works well because the location range is small (≤1000).

Approach 2: Use a Sorted Event List (Sweep Line) (Time: O(n log n), Space: O(n))

This method converts each trip into two events: a pickup event (start, +passengers) and a drop‑off event (end, -passengers). Collect all events and sort them by location. Then sweep from left to right while maintaining the current passenger count.

Whenever you encounter an event, update the running total. Drop‑offs reduce the count, pickups increase it. If the count exceeds capacity at any step, the trips cannot be completed. Sorting ensures events are processed in travel order. This pattern appears frequently in interval problems involving sorting and sweep‑line simulations.

Approach 3: Min‑Heap Trip Simulation (Time: O(n log n), Space: O(n))

Another simulation sorts trips by start location and tracks active trips in a min‑heap keyed by drop‑off location. As the car reaches a new pickup point, remove all trips from the heap whose drop‑off location is ≤ the current start. This frees capacity before boarding new passengers.

Push the current trip into the heap and add its passengers to the running count. If the count exceeds capacity, return false. The heap always holds ongoing trips ordered by the earliest drop‑off. This pattern resembles meeting‑room scheduling using a heap (priority queue).

Recommended for interviews: The difference array (prefix sum) approach is usually considered the cleanest and most optimal because it runs in linear time with minimal logic. The sorted event sweep line is more general and works even when the coordinate range is large. Showing the event simulation first demonstrates understanding of interval processing; presenting the prefix‑sum optimization shows strong algorithmic insight.

Approach 1: Simulate Passenger Count with Difference Array

We can simulate the number of passengers in the car at each kilometer using a difference array. For each trip, increase the passenger count at fromi and decrease it at toi. Then, iterate through this array to calculate the actual number of passengers at each point, checking if it ever exceeds the capacity.

The implementation maintains an array passengerChanges that models changes in the number of passengers at various kilometer points. We iterate over each trip, updating the number of passengers picked up and dropped off. Lastly, we traverse the passengerChanges calculating the current number of passengers and verifying it does not exceed the capacity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m) where n is the number of trips and m is the max distance (1000).
Space Complexity: O(m) for the difference array.

Try this approach in the editor →

Approach 2: Use a Sorted Event List

In this approach, we treat each pick-up and drop-off as events. We collect all events, sort them based on location, and then simulate the process of picking up and dropping off passengers by iterating through events in order, checking if it ever exceeds the car's capacity.

We build an array of events, each indicating a change in passenger count, either a pick-up or drop-off, and sort events by time. As we process the events, we update a counter and ensure it never exceeds capacity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), driven by sorting events.
Space Complexity: O(n).

Try this approach in the editor →

Approach 3: 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.

The time complexity is O(n), and the space complexity is O(M). Here, n is the number of trips, and M is the maximum end point in the trips. In this problem, M \le 1000.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate Passenger Count with Difference Array

Time Complexity: O(n + m) where n is the number of trips and m is the max distance (1000).
Space Complexity: O(m) for the difference array.

Use a Sorted Event List

Time Complexity: O(n log n), driven by sorting events.
Space Complexity: O(n).

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Difference Array / Prefix SumO(n + m)O(m)Best when location range is small and fixed. Fastest implementation.
Sorted Event List (Sweep Line)O(n log n)O(n)General interval processing when coordinates may be large.
Min Heap SimulationO(n log n)O(n)Useful when actively tracking ongoing trips ordered by earliest drop‑off.

Video Solution

Car Pooling - Leetcode 1094 - Python • NeetCode • 38,312 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Car Pooling easy or hard?
Car Pooling is generally classified as a medium difficulty problem. The logic becomes straightforward once you recognize it as a prefix sum or interval sweep line problem, but identifying that pattern can take practice.
Car Pooling Python/Java solution
Python and Java implementations usually follow either the prefix sum technique or the event sorting approach. Both languages handle this problem efficiently using arrays for the difference array method or built‑in sorting utilities for the sweep line solution.
How to solve Car Pooling in O(n)?
Use a difference array with prefix sum. For each trip, add passengers at the start index and subtract them at the end index. Then iterate through the array computing the cumulative sum. If the running passenger count ever exceeds capacity, return false.
What is the best approach for Car Pooling?
The prefix sum (difference array) approach is typically the most efficient. It records passenger changes at pickup and drop‑off points and computes a running total with a prefix sum. This runs in O(n + m) time where m is the location range, which is faster than sorting-based solutions.
Is Car Pooling asked at Google/Amazon/Meta?
Car Pooling is a common interval and simulation problem similar to questions asked in Google, Amazon, and Meta interviews. It tests understanding of sweep line techniques, prefix sums, and priority queue simulations used in scheduling problems.
What data structure is used in Car Pooling?
Typical solutions use arrays for difference arrays or prefix sums, sorted lists for sweep line events, and sometimes a min‑heap (priority queue) to track ongoing trips by earliest drop‑off location.
What is the time complexity of Car Pooling?
Time complexity depends on the approach. The difference array solution runs in O(n + m), where n is the number of trips and m is the maximum location index. Sorting or heap-based simulations take O(n log n) because events or trips must be sorted or managed in a priority queue.

Ready to solve this problem?

Practice Car Pooling with our built-in code editor and test cases.

Practice on FleetCode
Previous

Meeting Rooms II