Jobs

Interviews

Discussions

Car Pooling

Medium

Lyft

1 view

Topics:

ArraysGreedy Algorithms

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⁵

Car Pooling

Medium

Lyft

1 view

Topics:

ArraysGreedy Algorithms

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

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⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the capacity, the number of trips, the number of passengers, the start location, and the end location? Specifically, what are the maximum and minimum possible values for each of these?
Are the start and end locations guaranteed to be non-negative integers? Are they within a specific range, such as representing indices along a route?
Can multiple trips have the same start or end location? How should overlapping trips at the same location be handled?
If it's impossible to complete all trips within the car's capacity, should I return false, or should I throw an exception, or is there another specific error handling requirement?
Is the input array guaranteed to be valid, or should I handle cases where a trip has an invalid number of passengers (e.g., negative) or an invalid start/end location (e.g., end < start)?

Brute Force Solution

Approach

The brute force method for car pooling is like simulating the entire journey, stop by stop. At each stop, we carefully track how many passengers are in the car and see if we ever exceed the car's capacity. If we never exceed the capacity throughout the entire journey, then the car pooling is possible.

Here's how the algorithm would work step-by-step:

Imagine the car starts with zero passengers.
Go through each mile of the journey, one mile at a time.
For each mile, check if any passengers are getting in the car at that location.
Add the number of passengers getting in to the current number of passengers in the car.
Then, check if any passengers are getting out of the car at that same location.
Subtract the number of passengers getting out from the current number of passengers in the car.
After each mile, verify if the number of passengers in the car exceeds the car's capacity.
If, at any mile, the number of passengers exceeds the capacity, then the car pooling is not possible. Stop here.
If you reach the end of the journey (the last mile) and the car's capacity was never exceeded, then the car pooling is possible.

Code Implementation

def car_pooling_brute_force(trips, capacity):    max_location = 0
    for num_passengers, start_location, end_location in trips:
        max_location = max(max_location, end_location)

    current_passengers = 0
    # Iterate through each location to simulate the journey
    for location in range(max_location + 1):

        # Check for passengers getting off at the current location
        for num_passengers, start_location, end_location in trips:
            if end_location == location:
                current_passengers -= num_passengers

        # Check if capacity is exceeded at any point.
        if current_passengers > capacity:
            return False

        # Check for passengers getting on at the current location
        for num_passengers, start_location, end_location in trips:
            if start_location == location:
                current_passengers += num_passengers

        # Important: Verify capacity *after* passengers get on.
        if current_passengers > capacity:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m + n) – The solution iterates through each mile of the journey, where 'm' represents the maximum distance traveled (the furthest destination among all trips). For each mile, it then iterates through the list of trips ('n') to check if any passengers are boarding or alighting at that mile. Therefore, the time complexity is driven by iterating up to 'm' miles and, for each mile, potentially examining all 'n' trips. In the worst case, this results in m * n operations. However, if m is significantly larger than n, and we preprocess the trips to store boarding and alighting events at each mile in a more efficient manner (e.g., using a map), the iteration over the miles becomes the dominant factor. The complexity can be expressed as O(m + n) if we assume pre-processing the trips takes O(n) time and we iterate a maximum of m times. This simplifies to O(m) if we assume pre-processing the array is negligible, but the most precise answer is O(m + n) because the pre-processing time complexity of O(n) must be accounted for and added.

Space Complexity

O(1) – The brute force approach iterates through each mile of the journey, but it doesn't use any auxiliary data structures that scale with the number of trips or the maximum trip distance. It only keeps track of a constant number of variables such as the current number of passengers and the car's capacity, regardless of the input size (number of trips or distance). Therefore, the space complexity is constant.

Optimal Solution

Approach

The car pooling problem is efficiently solved by tracking the number of passengers entering and exiting the car at each location. We can determine if the car's capacity is ever exceeded by carefully observing these passenger changes. This avoids checking every possible combination of trips and focuses on the cumulative effect of each trip along the route.

Here's how the algorithm would work step-by-step:

Imagine the car's route as a series of stops along a line.
For each trip, note where passengers get on and where they get off.
Create a record of how the number of passengers changes at each stop: passengers getting on increase the count, and passengers getting off decrease it.
Go through these changes stop by stop, keeping a running total of how many passengers are in the car at any given time.
At each stop, check if the number of passengers ever exceeds the car's maximum capacity.
If the car is ever over its capacity at any stop, then it's impossible to complete all the trips; otherwise, it's possible.

Code Implementation

def car_pooling(trips, car_capacity):
    passenger_changes = [0] * 1001

    for trip in trips:
        number_of_passengers, start_location, end_location = trip
        # Passengers get on at the start location
        passenger_changes[start_location] += number_of_passengers

        # Passengers get off at the end location
        passenger_changes[end_location] -= number_of_passengers

    current_passengers = 0
    # Iterate through each location to track passengers
    for change in passenger_changes:
        current_passengers += change

        # Check if the car's capacity is exceeded
        if current_passengers > car_capacity:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the trips array once to record passenger changes at each location, effectively creating a timeline of passenger activity. This step is proportional to the number of trips (n). Subsequently, it iterates through this timeline (which has at most 1001 elements, based on the problem constraints since locations are between 0 and 1000), simulating the car's journey and checking if the capacity is ever exceeded. Since the timeline iteration is bounded by a constant (1001), the overall time complexity is dominated by the initial iteration through the trips array, resulting in O(n).

Space Complexity

O(N) – The algorithm creates a record of passenger changes at each stop along the route. In the worst case, each trip could have a unique start and end location, resulting in a number of stops proportional to the number of trips. This record, which is essentially an array or list tracking passenger changes, would then grow linearly with the number of trips, N, where N is the number of trips. Therefore, the auxiliary space required is O(N).

Edge Cases

Case	How to Handle
Empty trips array	Return true immediately as there are no trips to process and thus the capacity is never exceeded.
Null trips array	Throw an IllegalArgumentException or return false to indicate an invalid input.
Zero capacity	Return false if there are any trips with passengers, otherwise return true (no trips, zero capacity is fine).
Large number of trips with overlapping intervals that significantly exceed capacity	The algorithm should efficiently handle the accumulation of passengers at each location and correctly determine if the capacity is exceeded at any point.
Trips with start and end locations being the same	These trips have no impact and can be ignored or treated as a passenger pickup and immediate drop-off, adding and subtracting from the current passengers but not impacting subsequent locations.
Start locations are not sorted; End locations are before start locations	Sorting the locations based on start and then end location is crucial for accurate passenger tracking and the algorithm needs to account for end locations being before the start locations of other trips.
Integer overflow when accumulating passengers at a location	Use a data type with a larger range (e.g., long) to store the number of passengers at each location or implement checks to prevent overflow.
Trips with negative passenger count	Throw an exception or return false as the negative passenger count does not make sense in context of car pooling.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the capacity, the number of trips, the number of passengers, the start location, and the end location? Specifically, what are the maximum and minimum possible values for each of these?
Are the start and end locations guaranteed to be non-negative integers? Are they within a specific range, such as representing indices along a route?
Can multiple trips have the same start or end location? How should overlapping trips at the same location be handled?
If it's impossible to complete all trips within the car's capacity, should I return false, or should I throw an exception, or is there another specific error handling requirement?
Is the input array guaranteed to be valid, or should I handle cases where a trip has an invalid number of passengers (e.g., negative) or an invalid start/end location (e.g., end < start)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the car starts with zero passengers.
Go through each mile of the journey, one mile at a time.
For each mile, check if any passengers are getting in the car at that location.
Add the number of passengers getting in to the current number of passengers in the car.
Then, check if any passengers are getting out of the car at that same location.
Subtract the number of passengers getting out from the current number of passengers in the car.
After each mile, verify if the number of passengers in the car exceeds the car's capacity.
If, at any mile, the number of passengers exceeds the capacity, then the car pooling is not possible. Stop here.
If you reach the end of the journey (the last mile) and the car's capacity was never exceeded, then the car pooling is possible.

Code Implementation

def car_pooling_brute_force(trips, capacity):    max_location = 0
    for num_passengers, start_location, end_location in trips:
        max_location = max(max_location, end_location)

    current_passengers = 0
    # Iterate through each location to simulate the journey
    for location in range(max_location + 1):

        # Check for passengers getting off at the current location
        for num_passengers, start_location, end_location in trips:
            if end_location == location:
                current_passengers -= num_passengers

        # Check if capacity is exceeded at any point.
        if current_passengers > capacity:
            return False

        # Check for passengers getting on at the current location
        for num_passengers, start_location, end_location in trips:
            if start_location == location:
                current_passengers += num_passengers

        # Important: Verify capacity *after* passengers get on.
        if current_passengers > capacity:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the car's route as a series of stops along a line.
For each trip, note where passengers get on and where they get off.
Create a record of how the number of passengers changes at each stop: passengers getting on increase the count, and passengers getting off decrease it.
Go through these changes stop by stop, keeping a running total of how many passengers are in the car at any given time.
At each stop, check if the number of passengers ever exceeds the car's maximum capacity.
If the car is ever over its capacity at any stop, then it's impossible to complete all the trips; otherwise, it's possible.

Code Implementation

def car_pooling(trips, car_capacity):
    passenger_changes = [0] * 1001

    for trip in trips:
        number_of_passengers, start_location, end_location = trip
        # Passengers get on at the start location
        passenger_changes[start_location] += number_of_passengers

        # Passengers get off at the end location
        passenger_changes[end_location] -= number_of_passengers

    current_passengers = 0
    # Iterate through each location to track passengers
    for change in passenger_changes:
        current_passengers += change

        # Check if the car's capacity is exceeded
        if current_passengers > car_capacity:
            return False

    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty trips array	Return true immediately as there are no trips to process and thus the capacity is never exceeded.
Null trips array	Throw an IllegalArgumentException or return false to indicate an invalid input.
Zero capacity	Return false if there are any trips with passengers, otherwise return true (no trips, zero capacity is fine).
Large number of trips with overlapping intervals that significantly exceed capacity	The algorithm should efficiently handle the accumulation of passengers at each location and correctly determine if the capacity is exceeded at any point.
Trips with start and end locations being the same	These trips have no impact and can be ignored or treated as a passenger pickup and immediate drop-off, adding and subtracting from the current passengers but not impacting subsequent locations.
Start locations are not sorted; End locations are before start locations	Sorting the locations based on start and then end location is crucial for accurate passenger tracking and the algorithm needs to account for end locations being before the start locations of other trips.
Integer overflow when accumulating passengers at a location	Use a data type with a larger range (e.g., long) to store the number of passengers at each location or implement checks to prevent overflow.
Trips with negative passenger count	Throw an exception or return false as the negative passenger count does not make sense in context of car pooling.