Car Pooling solution and explanation
Infosys
Google
9 more videos on this problem
Car Pooling - Leetcode 1094 - PythonNeetCode · 14:45 · 38K views
Car Pooling | Leetcode #1094Techdose · 18:31 · 12K views
Car Pooling | Leetcode 1094 | Line Sweep Technique Concepts & Questions - 6 | codestorywithMIKcodestorywithMIK · 14:42 · 4K views
1094. Car Pooling Leetcode Daily Challenge 2 Approaches Map and Vector with Examples and Full CodeCode with Alisha · 10:11 · 3K views
LeetCode 1094. Car Pooling Solution Explained - JavaAlgorithms and Data Structures Course · 15:49 · 2K views
Car Pooling | Leet code 1094 | Theory explained + Python codeSai Anish Malla · 8:18 · 2K views
CAR POOLING | LEETCODE # 1094 | PYTHON HEAP SOLUTIONCracking FAANG · 15:47 · 1K views
Leetcode - Car Pooling (Python)Timothy H Chang · 8:41 · 918 views
Car Pooling Leetcode 1094 videoEasyLeetcode · 8:53 · 694 views
LeetCode 1094 Car Pooling - Java Solution Using Sorting & Prioriry Queue Explained With ExamplesAlgorithmicIQ · 23:48 · 567 views
The problem
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 <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= 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.
def carPooling(trips, capacity):
passenger_changes = [0] * 1001
for num_passengers, start, end in trips:
passenger_changes[start] += num_passengers
passenger_changes[end] -= num_passengers
current_passengers = 0
for change in passenger_changes:
current_passengers += change
if current_passengers > capacity:
return False
return Truepublic class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] passengerChanges = new int[1001];
for (int[] trip : trips) {
passengerChanges[trip[1]] += trip[0];
passengerChanges[trip[2]] -= trip[0];
}
int currentPassengers = 0;
for (int change : passengerChanges) {
currentPassengers += change;
if (currentPassengers > capacity) return false;
}
return true;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
int passengerChanges[1001] = {0};
for(const auto& trip : trips) {
passengerChanges[trip[1]] += trip[0];
passengerChanges[trip[2]] -= trip[0];
}
int currentPassengers = 0;
for(int i = 0; i < 1001; ++i) {
currentPassengers += passengerChanges[i];
if (currentPassengers > capacity) return false;
}
return true;
}
};var carPooling = function(trips, capacity) {
let passengerChanges = new Array(1001).fill(0);
for (let [numPassengers, from, to] of trips) {
passengerChanges[from] += numPassengers;
passengerChanges[to] -= numPassengers;
}
let currentPassengers = 0;
for (let change of passengerChanges) {
currentPassengers += change;
if (currentPassengers > capacity) return false;
}
return true;
};#include <stdbool.h>
#include <string.h>
bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
int passengerChanges[1001];
memset(passengerChanges, 0, sizeof(passengerChanges));
for(int i = 0; i < tripsSize; i++) {
int numPassengers = trips[i][0];
int from = trips[i][1];
int to = trips[i][2];
passengerChanges[from] += numPassengers;
passengerChanges[to] -= numPassengers;
}
int currentPassengers = 0;
for(int i = 0; i < 1001; i++) {
currentPassengers += passengerChanges[i];
if(currentPassengers > capacity) {
return false;
}
}
return true;
}public class Solution {
public bool CarPooling(int[][] trips, int capacity) {
int[] passengerChanges = new int[1001];
foreach (var trip in trips) {
passengerChanges[trip[1]] += trip[0];
passengerChanges[trip[2]] -= trip[0];
}
int currentPassengers = 0;
foreach (var change in passengerChanges) {
currentPassengers += change;
if (currentPassengers > capacity) return false;
}
return true;
}
}A list passenger_changes schema simulates the number of passengers at any point. Passengers are adjusted using trip data, and evaluation ensures that counts remain within limits.
Time Complexity: O(n + m), with n as trip counts and m as the number of distance steps (1000).
Space Complexity: O(m).
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.
def carPooling(trips, capacity):
events = []
for num_passengers, start, end in trips:
events.append((start, num_passengers))
events.append((end, -num_passengers))
events.sort()
current_passengers = 0
for _, change in events:
current_passengers += change
if current_passengers > capacity:
return False
return Trueimport java.util.*;
public class Solution {
public boolean carPooling(int[][] trips, int capacity) {
List<int[]> events = new ArrayList<>();
for (int[] trip : trips) {
events.add(new int[]{trip[1], trip[0]}); // pickup
events.add(new int[]{trip[2], -trip[0]}); // drop-off
}
events.sort((a, b) -> a[0] - b[0]);
int currentPassengers = 0;
for (int[] event : events) {
currentPassengers += event[1];
if (currentPassengers > capacity) return false;
}
return true;
}
}#include <vector>
#include <algorithm>
class Solution {
public:
bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
std::vector<std::pair<int, int>> events;
for (const auto& trip : trips) {
events.emplace_back(trip[1], trip[0]); // pickup event
events.emplace_back(trip[2], -trip[0]); // drop-off event
}
std::sort(events.begin(), events.end());
int currentPassengers = 0;
for (const auto& [time, change] : events) {
currentPassengers += change;
if (currentPassengers > capacity) return false;
}
return true;
}
};var carPooling = function(trips, capacity) {
let events = [];
for (let [numPassengers, from, to] of trips) {
events.push([from, numPassengers]); // pickup
events.push([to, -numPassengers]); // drop-off
}
events.sort((a, b) => a[0] - b[0]);
let currentPassengers = 0;
for (let [time, change] of events) {
currentPassengers += change;
if (currentPassengers > capacity) return false;
}
return true;
};#include <stdbool.h>
#include <stdlib.h>
typedef struct {
int time;
int passengers;
} Event;
int cmpEvent(const void* a, const void* b) {
return ((Event*)a)->time - ((Event*)b)->time;
}
bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
Event events[2 * tripsSize];
int index = 0;
for(int i = 0; i < tripsSize; i++) {
events[index++] = (Event){trips[i][1], trips[i][0]};
events[index++] = (Event){trips[i][2], -trips[i][0]};
}
qsort(events, 2 * tripsSize, sizeof(Event), cmpEvent);
int currentPassengers = 0;
for(int i = 0; i < 2 * tripsSize; i++) {
currentPassengers += events[i].passengers;
if(currentPassengers > capacity) {
return false;
}
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool CarPooling(int[][] trips, int capacity) {
List<int[]> events = new List<int[]>();
foreach (var trip in trips) {
events.Add(new int[]{trip[1], trip[0]}); // pickup
events.Add(new int[]{trip[2], -trip[0]}); // drop-off
}
events.Sort((a, b) => a[0] - b[0]);
int currentPassengers = 0;
foreach (var ev in events) {
currentPassengers += ev[1];
if (currentPassengers > capacity) return false;
}
return true;
}
}Events are articulated for pick-up and drop-off, indexed and sorted by location metrics. Processing concurrently evaluates car load limits.
Time Complexity: O(n log n) from event sorting.
Space Complexity: O(n).
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.
function carPooling(trips: number[][], capacity: number): boolean {
const mx = Math.max(...trips.map(([, , t]) => t));
const d = Array(mx + 1).fill(0);
for (const [x, f, t] of trips) {
d[f] += x;
d[t] -= x;
}
let s = 0;
for (const x of d) {
s += x;
if (s > capacity) {
return false;
}
}
return true;
}func carPooling(trips [][]int, capacity int) bool {
d := [1001]int{}
for _, trip := range trips {
x, f, t := trip[0], trip[1], trip[2]
d[f] += x
d[t] -= x
}
s := 0
for _, x := range d {
s += x
if s > capacity {
return false
}
}
return true
}impl Solution {
pub fn car_pooling(trips: Vec<Vec<i32>>, capacity: i32) -> bool {
let mx = trips.iter().map(|e| e[2]).max().unwrap_or(0) as usize;
let mut d = vec![0; mx + 1];
for trip in &trips {
let (x, f, t) = (trip[0], trip[1] as usize, trip[2] as usize);
d[f] += x;
d[t] -= x;
}
d.iter()
.scan(0, |acc, &x| {
*acc += x;
Some(*acc)
})
.all(|s| s <= capacity)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate Passenger Count with Difference Array | Time Complexity: O(n + m), with n as trip counts and m as the number of distance steps (1000). |
| Use a Sorted Event List | Time Complexity: O(n log n) from event sorting. |
| Difference Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Difference Array / Prefix Sum | O(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 Simulation | O(n log n) | O(n) | Useful when actively tracking ongoing trips ordered by earliest drop‑off. |
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.