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.

Description Hints 1 Solution Video 14:45

1094. Car Pooling

Medium56.5% acceptance12 companies

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] = [numPassengers_i, from_i, to_i] indicates that the i^th trip has numPassengers_i passengers and the locations to pick them up and drop them off are from_i and to_i 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 <= numPassengers_i <= 100
0 <= from_i < to_i <= 1000
1 <= capacity <= 10⁵

Asked at 12 companies

Careem Lyft Zepto Paytm Goldman Sachs Flipkart Amazon Meta

Infosys

Google Microsoft Bloomberg

Topics

Hints open one at a time

Hint 1

Sort the pickup and dropoff events by location, then process them in order.

14:45

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution