1094. Car Pooling
Problem Description
In this problem, we are simulating a carpool scenario. A car has a certain number of empty seats (given by capacity
), and it can only drive in one directionāeast. We are provided with an array trips
, where each element is a trip described by three integers: numPassengers
, from
, and to
. These respectively represent the number of passengers for that trip, the kilometer mark where the passengers will be picked up, and the kilometer mark where they will be dropped off. Our task is to determine if the car can successfully complete all the given trips without ever exceeding its seating capacity. If it is possible to pick up and drop off all passengers for all the trips without going over capacity at any point, we return true
. Otherwise, we return false
.
Intuition
The key insight to solving this problem is recognizing that we don't actually have to simulate the driving of the car along the eastward path. Instead, we can focus on the changes in the number of passengers at each pick-up and drop-off location. The original trips array tells us how many passengers get on and off at specific points, so we can tally these changes as they occur over the course of the car's journey.
Imagine a timeline where each point is a kilometer mark where some action takes placeāa pick-up or a drop-off. We iterate through every trip and note the changes in passenger numbers at each relevant kilometer mark. The d
array in the solution serves as this timeline, with indexes representing kilometer marks and values representing the change in the number of passengers at that mark.
When a trip starts (from
), we add the number of passengers to the tally at that kilometer mark. When the trip ends (to
), we subtract the number of passengers from the tally at the drop-off kilometer mark, since those passengers are no longer in the car.
After tallying all passenger changes, we use the accumulate
function to simulate the succession of passengers over the journey. This function computes a running total that represents the number of passengers in the car at each kilometer mark. Finally, we check if this running total ever exceeds the car's capacity at any point. If it doesn't exceed the capacity, it means that the car can complete all trips successfully. Therefore, we return true
if the car's capacity is never exceeded, or false
if at some point there are too many passengers.
Learn more about Prefix Sum, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The solution utilizes a straightforward approach complemented by efficient use of data structures and algorithms. Here's a step-by-step breakdown of the implementation, showcasing the thought process behind the algorithm:
-
The first data structure introduced is an array
d
of size 1001, initialized with zeros. This array is essential for recording the change in the number of passengers at each location along the trip. Why size 1001? This accounts for the maximum potential distance (from
andto
values) that could be specified in the problem (assuming they are within a reasonable range). -
We loop through each trip in the trips array using a
for
loop. In each iteration, we destructure the trip intonumPassengers
,from
, andto
. We are not concerned with the order of trips since we are looking at the overall effect on the car's capacity at each kilometer mark. -
For each trip:
- At the pick-up location
from
, we increase the value in thed
array bynumPassengers
. - At the drop-off location
to
, we decrease the value in thed
array bynumPassengers
.
- At the pick-up location
-
The next step is to use the
accumulate
function from Python'sitertools
library. This function takes an iterable and returns a running total of the values. In our case, it generates a list where each element is the sum of passengers in the car up until that point. This list reflects the number of passengers present in the car at each kilometer mark of the journey. -
The final part of the solution involves checking if at any point the running total of passengers exceeds the car's capacity which is done using Python's
all()
function in conjunction with a generator expression. The expression insideall()
checks for every kilometer:s <= capacity
wheres
is an element from the running total obtained fromaccumulate(d)
. If all values are within capacity,all()
returnstrue
. -
The solution returns the result of this
all()
check. If the accumulated number of passengers at any point is greater than the car's capacity, the function will returnfalse
; otherwise, it will returntrue
indicating successful completion of all trips within the given constraints.
This approach allows us to solve the problem without directly simulating the trip progress, which would be less efficient. We make just two passes: one for updating the d
array, and another for accumulating and checking the sums against capacity, resulting in a time complexity that is linear with respect to the number of trips.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach.
Assume we are given the following parameters for our carpool problem:
capacity
: 4trips
: [[2, 1, 5], [3, 3, 7]]
Here, the car has 4 empty seats. There are two trips to consider:
- 2 passengers from kilometer 1 to kilometer 5
- 3 passengers from kilometer 3 to kilometer 7
Now, we will walk through the solution step by step.
-
We initialize an array
d
of size 1001 with all zeros.d = [0] * 1001
-
We loop through each trip to update
d
. In our example:- For the first trip [2, 1, 5]:
- at
from
kilometer 1, add 2 (d[1] += 2
) - at
to
kilometer 5, subtract 2 (d[5] -= 2
)
- at
- For the second trip [3, 3, 7]:
- at
from
kilometer 3, add 3 (d[3] += 3
) - at
to
kilometer 7, subtract 3 (d[7] -= 3
)
- at
After these updates, the array
d
would look like this (omitting zeros):d[1] = 2 d[3] = 3 d[5] = -2 d[7] = -3
- For the first trip [2, 1, 5]:
-
Next, we use the
accumulate
function to determine the number of passengers in the car at each point in the trip. Theaccumulate
function will process the arrayd
and give us:[0, 2, 2, 5, 5, 3, 3, 0, 0, ..., 0] // Accumulated passenger counts
This array represents the total number of passengers after each kilometer mark:
- 0 passengers at the start
- 2 passengers after kilometer 1
- No change until kilometer 3
- 5 passengers from kilometer 3 (since 2 were already in the car and 3 more joined)
- Capacity is exceeded at this point (5 passengers > 4 capacity)
- The count drops to 3 passengers after kilometer 5 (2 passengers leave)
- No change until kilometer 7
- All passengers have left by kilometer 7
-
Finally, we check if the
capacity
of the car is ever exceeded using theall()
function in conjunction with a generator expression:result = all(s <= capacity for s in accumulate(d))
Since
s
is 5 at some point which is greater than thecapacity
of 4, theall()
function would returnfalse
.
Therefore, our function that simulates whether all trips can be successfully completed given the capacity
, with the input provided, would return false
. The car cannot successfully complete all the given trips without exceeding its seating capacity.
Solution Implementation
1from itertools import accumulate # Import the accumulate function from itertools
2from typing import List # Import List for type annotation
3
4class Solution:
5 def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
6 # Initialize a list of zeros for all possible locations (0 to 1000)
7 location_deltas = [0] * 1001
8
9 # Loop over each trip in the trips list
10 for passengers, start_location, end_location in trips:
11 # Increase the passenger count at the start location
12 location_deltas[start_location] += passengers
13 # Decrease the passenger count at the end location
14 location_deltas[end_location] -= passengers
15
16 # Use accumulate to calculate the running total of passengers at each location
17 # and verify if at any point the capacity is exceeded
18 # all() will return True if all running totals are less than or equal to capacity
19 return all(current_passengers <= capacity for current_passengers in accumulate(location_deltas))
20
21# The code defines a class Solution with a method carPooling.
22# The method takes a list of trips (where each trip is a list of [passengers, start_location, end_location])
23# and the vehicle's capacity.
24# It returns True if the vehicle can accommodate all the trips without exceeding the capacity at any point.
25
1class Solution {
2
3 // The function checks if it's possible to pick up and drop off all passengers for all trips
4 public boolean carPooling(int[][] trips, int capacity) {
5 // Initialize an array to record the cumulative changes in passenger count at each stop.
6 int[] passengerChanges = new int[1001];
7
8 // Iterate over all trips to record passenger pick-ups and drop-offs.
9 for (int[] trip : trips) {
10 int numberOfPassengers = trip[0]; // The number of passengers for the trip
11 int startLocation = trip[1]; // The starting location for the trip
12 int endLocation = trip[2]; // The ending location for the trip
13
14 // Add the number of passengers to the start location
15 passengerChanges[startLocation] += numberOfPassengers;
16 // Subtract the number of passengers from the end location
17 passengerChanges[endLocation] -= numberOfPassengers;
18 }
19
20 // Initialize the current number of passengers in the car to 0.
21 int currentPassengers = 0;
22
23 // Iterate over each location to update the number of passengers after each pick-up/drop-off.
24 for (int change : passengerChanges) {
25 currentPassengers += change; // Update the current number of passengers.
26
27 // If the current number of passengers exceeds capacity, return false.
28 if (currentPassengers > capacity) {
29 return false;
30 }
31 }
32
33 // If we've successfully accounted for all trips without exceeding capacity, return true.
34 return true;
35 }
36}
37
1#include <vector>
2
3class Solution {
4public:
5 bool carPooling(std::vector<std::vector<int>>& trips, int capacity) {
6 // Create an array to keep track of changes in car capacity at each point.
7 int deltaCapacity[1001] = {0};
8
9 // Loop through the trips to record the changes in capacity.
10 for (const auto& trip : trips) {
11 int passengers = trip[0]; // Number of passengers in the trip
12 int from = trip[1]; // Starting point of the trip
13 int to = trip[2]; // End point of the trip
14
15 deltaCapacity[from] += passengers; // Increment passengers at the start
16 deltaCapacity[to] -= passengers; // Decrement passengers at the end
17 }
18
19 // Initialize the sum that will track current number of passengers in car
20 int currentPassengers = 0;
21
22 // Iterate through each point to calculate the capacity usage.
23 for (int pointChange : deltaCapacity) {
24 currentPassengers += pointChange; // Adjust the current capacity
25
26 // If at any point the number of passengers exceeds capacity, return false.
27 if (currentPassengers > capacity) {
28 return false;
29 }
30 }
31
32 // If we made it through all the points without exceeding capacity, return true.
33 return true;
34 }
35};
36
1function carPooling(trips: number[][], capacity: number): boolean {
2 // Create an array to hold the net number of passengers at each point
3 const deltaPassengers = new Array(1001).fill(0);
4
5 // Fill the deltaPassengers array with passenger changes at each point
6 for (const [numPassengers, start, end] of trips) {
7 // Add the passengers to the start location
8 deltaPassengers[start] += numPassengers;
9 // Subtract the passengers from the end location
10 deltaPassengers[end] -= numPassengers;
11 }
12
13 // Track the current number of passengers in the car
14 let currentPassengers = 0;
15
16 // Iterate through each point to determine if capacity is exceeded
17 for (const passengerChange of deltaPassengers) {
18 // Update the current number of passengers
19 currentPassengers += passengerChange;
20
21 // If the current passengers exceed the capacity, return false
22 if (currentPassengers > capacity) {
23 return false;
24 }
25 }
26
27 // If the loop finishes without returning false, the carpooling is possible within the capacity
28 return true;
29}
30
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n + m), where n
is the length of the trips
array and m
is the range of possible stops (fixed at 1001 in this case). The loop iterates over all elements in trips
once, which results in O(n) time. The accumulate
function processes the differential list which is of size m, taking O(m) time. Therefore, the total time complexity is the sum of these two parts, O(n + m).
Space Complexity
The space complexity of the code is O(m), where m
is the fixed range of 1001 for the possible stops. The list d
is created with a size of 1001 to track the number of passengers getting on and off at each stop. No other significant space is used, so the space complexity is determined by the size of this list, which is O(m).
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Donāt Miss This!