Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.2.
Explanation
3.
Naive Approach
3.1.
Algorithm
3.2.
C++ Code
3.2.1.
Output
3.3.
Java Code
3.3.1.
Output
3.4.
Complexity Analysis
4.
Greedy Approach
4.1.
Explanation
4.2.
Algorithm
4.3.
C++ Function
4.3.1.
Output
4.4.
Java Implementation
4.4.1.
Output
4.5.
Complexity Analysis
4.5.1.
Time Complexity 
4.5.2.
Space Complexity
5.
Prefix Sum Approach
5.1.
Dry Run
5.2.
Implementation in C++
5.2.1.
Output
5.3.
Java Implementation
5.3.1.
Output
5.4.
Complexity
5.4.1.
Time complexity
5.4.2.
Space complexity
6.
Frequently Asked Questions
6.1.
What is pre-computation in Problem-solving?
6.2.
What are some applications of the carpooling problem in real-world scenarios?
6.3.
How does a Priority Queue differ from a regular Queue?
6.4.
What is the Time Complexity of the Naive approach?
6.5.
What operations can be performed on a Priority Queue?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Car Pooling

Author Yogesh Kumar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Hello Ninja, Welcome back to another problem. The Car Pooling problem is a classic optimisation problem in DSA that involves efficiently matching people who need to travel to the same destination.

Introduction

We’ll go over all the methods, including brute force and the most efficient way to solve this problem. 

Are you ready to go through this article?

Then let's start with the problem statement to think about the approaches for this problem. 

Also read about the topic, kth largest element in an array and Euclid GCD Algorithm

Problem Statement

Given a car with a certain capacity for empty seats, the vehicle can only drive in one direction, and initially, the car is at starting point. There is an array of trips, where each trip is represented by a list of 3 integers:

  • total_passengers: number of passengers for the trip.
     
  • start_from: the starting point of the trip, represented as the number of kilometres due from the car's starting point.
     
  • end_to: the ending point of the trip, represented as the number of kilometres due from the car's starting point.
     

The task is to determine if it is possible to pick up and drop off all passengers for all the given trips. The solution should return true if it is possible and false otherwise.

Example

trips = [[1, 1, 3], [2, 2, 6], [3, 5, 9]]

capacity = 5

Output = true

Explanation

So, on the first trip [1,1,3], one passenger travels from 1 to 3. From 2 two more passengers are added by the trip second [2,2,6], and the total passenger becomes 3. At 3 first trip ends, and the total number of passengers becomes 2. The number of passengers remained the same till 5 where 3 passengers added at 5 by trip third, so total passengers become 5. At 6 the second trip ends, and the total number of passengers becomes 3 and remains the same till 9. 

Which follows the capacity of the car, which is 5.

Explanation
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Naive Approach

In this approach, we understand the problem with the example above. The problem requires us to determine if it is possible to pick up and drop off all passengers for all the given trips. To do this, we can simulate the trips and keep track of the number of passengers in the car at each point.

We start by initialising a variable to keep track of the current number of passengers in the car to 0. Then, we iterate through each trip and do the following for each trip. At any point in time when the total passengers are greater than capacity, return false and at the end, return true.

Algorithm

1.Declare an array that stores the people still in the car for the journey.

2. Now run a loop for the trip length regarding the number of sub-trips in the trip list.

3. Iterate over the sub-trips and compute the number of people currently in the car with a total capacity.

Algorithm

4. If people number at any particular distance in a car greater than the capacity and how many sub-trips, we have to return the false otherwise, iterate over the loop.

5. We have to return true at the end. If the number of passengers never exceeds the capacity of the car during any point in the trip, return true.

C++ Code

#include <iostream>
#include <vector>

using namespace std;

bool car_Pooling(vector<vector<int>>& trips, int capacity) {
    
    // Initialize an array of size 1001 with all elements as 0
    int arr[1001] = {0};
    
    // For each trip, add the number of passengers to the corresponding indices of the array
    for(int i=0;i<trips.size();i++){
        for(int j=trips[i][1];j<trips[i][2];j++){
            arr[j] += trips[i][0];
            if(arr[j] > capacity){
                
                // If the number of passengers exceeds the capacity of the car at any point in the trip, return false
                return false;
            }
        }
    }
    
    // If the number of passengers never exceeds the capacity of the car during any point in the trip, return true
    return true;
}

int main() {
    // Hardcoded input
    vector<vector<int>> trips = {{1,1,3}, {2,2,6}, {3,5,9}};
    
    int capacity = 5;
    
    
    bool canTransport = car_Pooling(trips, capacity);
    
    if(canTransport) {
        cout << "All passengers can be transported" << endl;
    } else {
        cout << "Not all passengers can be transported" << endl;
    }
    return 0;
}

Output

Output

Java Code

import java.util.*;

public class CodingNinjaSolution {

    public boolean carPooling(int[][] trips, int capacity) {
        // Initialize an integer array of size 1001 with all elements set to 0
        int[] arr = new int[1001];
       
        // For each trip, add the number of passengers to the corresponding indices of the array
        for (int i = 0; i < trips.length; i++) {
            for (int j = trips[i][1]; j < trips[i][2]; j++) {
                arr[j] += trips[i][0];
                if (arr[j] > capacity) {
                    // If the number of passengers exceeds the capacity of the car at any point in the trip, return false
                    return false;
                }
            }
        }
       
        // If the number of passengers never exceeds the capacity of the car during any point in the trip, return true
        return true;
    }

    public static void main(String[] args) {
        // Hardcoded input
        int[][] trips = {{1,1,3}, {2,2,6}, {3,5,9}};
        int capacity = 5;

        // Create an instance of the CodingNinjaSolution class
        CodingNinjaSolution solution = new CodingNinjaSolution();

        // Call the carPooling function with the hardcoded input and print the result
        boolean canTransport = solution.carPooling(trips, capacity);
        if (canTransport) {
            System.out.println("All passengers can be transported");
        } else {
            System.out.println("Not all passengers can be transported");
        }
    }
}

Output

Output

Complexity Analysis

Now talking about the Complexity of the Code, As we have to iterate over the sub-trip present in the array, then we have the start and endpoint for the loop for which we are running for O(end point-start point) times and a trip for the length of trip, so its O(N^2) and Space complexity is O(N) as for extra array for maintaining people strength in the car.

Greedy Approach

The Greedy approach to solve this problem involves sorting the trips array based on the start location, creating a priority queue to track current passengers in the car, and iterating over the trips array to remove passengers who have reached their destination, add new passengers to the car, and check if the car capacity is exceeded at any point.

Explanation

This is the explanation of the Greedy approach using the input trips = [[1, 1, 3], [2, 2, 6], [3, 5, 9]], capacity = 5:

  • Sort the trips array based on the start location of each trip: [[1, 1, 3], [2, 2, 6], [3, 5, 9]].
Sort the trips
  • Create a priority queue (min-heap) to track the current passengers in the car, sorted by their end location. Initially, the queue is empty: queue = [].
Create a priority queue
  • Iterate over the sorted trips array:
     

Trip 1: queue = [(1, 3)], where (1, 3) represents one passenger with start location 1 and end location 3.

iterate over the sorted trips array:

Trip 2: queue = [(1, 3), (2, 6)].

iterate over the sorted trips array:

Trip 3: queue = [(1, 3)], since passenger (2, 6) is removed from the queue when its trip ends, and passenger (3, 9) is added to the queue under the capacity.

iterate over the sorted trips array:
  • Since the car never has more than 5 passengers at any point in the trip, the function returns true.
return funcrion

Algorithm

Here is the algorithm for the above approach for solving the carpooling problem:

  • Sort the trips array based on the start location of each trip.
     
  • Create a priority queue to track the current passengers in the car.
     
  • Iterate over the trips array.
     
  • For each trip, remove any passengers who have completed their trips from the priority queue by checking if their end location is less than or equal to the current trip's start location, and add their capacity back to the car's total capacity.
     
  • Check if there is enough capacity in the car for the current trip. If not, return false.
     
  • If there is enough capacity, subtract the number of passengers for the current trip from the car's total capacity, and add the end location of the trip to the priority queue.
     
  • If all trips are completed, and the car has enough capacity for each trip, return true.

C++ Function

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;



bool carPooling(vector<vector<int>>& trips, int capacity) {
    // Sort trips based on start location
    sort(trips.begin(), trips.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    // Create a priority queue to track current passengers
    priority_queue<pair<int, int>, vector<pair<int, int>>,   greater<pair<int, int>>> pq;

    // Iterate over trips and update priority queue
    for (const auto& trip : trips) {
        int num_passengers = trip[0];
        int start_location = trip[1];
        int end_location = trip[2];

        // Remove passengers who have completed their trips
        while (!pq.empty() && pq.top().first <= start_location) {
            capacity += pq.top().second;
            pq.pop();
        }

        // If there is not enough capacity for the current trip, return false
        if (capacity < num_passengers) {
            return false;
        }

        // Add current passengers to the priority queue
        capacity -= num_passengers;
        pq.push({end_location, num_passengers});
    }

  return true;
}

int main() {
    // Hardcoded input
    vector<vector<int>> trips = {{1,1,3}, {2,2,6}, {3,5,9}};
    int capacity = 5;

    bool result = carPooling(trips, capacity);

    // Print result
    if (result) {
        cout << "It is possible to transport all passengers within the given capacity." << endl;
    } else {
        cout << "It is not possible to transport all passengers within the given capacity." << endl;
    }

    return 0;
}

Output

Output

Java Implementation

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.AbstractMap;

public class CodingNinjaSolution {
    public boolean carPooling(int[][] trips, int capacity) {
        // Sort trips based on start location
        Arrays.sort(trips, (a, b) -> Integer.compare(a[1], b[1]));

        // Create a priority queue to track current passengers
        PriorityQueue<AbstractMap.SimpleEntry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.getKey(), b.getKey()));

        // Iterate over trips and update priority queue
        for (int[] trip : trips) {
            int numPassengers = trip[0];
            int startLocation = trip[1];
            int endLocation = trip[2];

            // Remove passengers who have completed their trips
            while (!pq.isEmpty() && pq.peek().getKey() <= startLocation) {
                capacity += pq.poll().getValue();
            }

            // If there is not enough capacity for the current trip, return false
            if (capacity < numPassengers) {
                return false;
            }

            // Add current passengers to the priority queue
            capacity -= numPassengers;
            pq.offer(new AbstractMap.SimpleEntry<>(endLocation, numPassengers));
        }

        return true;
    }
    
    public static void main(String[] args) {
        // Hardcoded input
        int[][] trips = {{1,1,3}, {2,2,6}, {3,5,9}};
        int capacity = 5;

        CodingNinjaSolution s = new CodingNinjaSolution();
        boolean result = s.carPooling(trips, capacity);

        // Print result
        if (result) {
            System.out.println("It is possible to transport all passengers within the given capacity.");
        } else {
            System.out.println("It is not possible to transport all passengers within the given capacity.");
        }
    }
}

Output

Output

Complexity Analysis

Time Complexity 

O(NlogN), where N is the number of elements in trips.

Reason: In the above code, The first operation in the code is sorting the trips based on the start location using sort() operation. This operation has a time complexity of O(n log n), where n is the number of trips.

Then, we iterate over each trip and perform several operations. The while loop that removes passengers who have completed their trips can run at most n times in the worst-case scenario, as each trip can have at most one passenger. The time complexity of the while loop is O(log n) for each iteration, as it requires removing the smallest element from the priority queue.

Space Complexity

O(N), where N is the number of elements in trips.

Reason: In the above code, we use a time vector of size 1001 to store the change in the number of passengers at each time. Hence, the space complexity is O(1001).

Prefix Sum Approach

We can optimize through the prefix sum method by keeping track of the total number of passengers at each location using a prefix sum array, which allows us to check if the number of passengers at any location exceeds the given capacity in constant time. This reduces the algorithm's time complexity from O(n log n) to O(n).

Dry Run

For the below example:

trips = {{1,1,3}, {2,2,6}, {3,5,9}};

capacity = 5;
 

  • We initialise the prefixSum array with 1001 elements, all set to 0.
     
  • We iterate over the trips array and update the prefix sum array as follows:

    • For the first trip {1,1,3}, we add one passenger to location 1 and subtract one passenger from location 3.
       
    • For the second trip {2,2,6}, we add two passengers to location 2 and subtract two passengers from location 6.
       
    • For the third trip {3,5,9}, we add three passengers to location 5 and subtract three passengers from location 9.


We iterate over the prefix sum array and keep track of the available capacity. At each location, we subtract the number of passengers from the capacity. If the capacity becomes negative at any point, we return false. Otherwise, we return true if we complete the iteration without hitting a negative capacity.
Since the capacity never becomes negative from 1 to 9, we return true.

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

class CodingNinjaSolution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> prefixSum(1001, 0); // 1001 is the maximum possible end location

        // Calculate the prefix sum of passengers at each location
        for (auto& trip : trips) {
            prefixSum[trip[1]] += trip[0];
            prefixSum[trip[2]] -= trip[0];
        }

        // Iterate over the prefix sum and check capacity at each location
        for (int i = 0; i < prefixSum.size(); i++) {
            capacity -= prefixSum[i];
            if (capacity < 0) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    // Hardcoded input
    vector<vector<int>> trips = {{1,1,3}, {2,2,6}, {3,5,9}};
    int capacity = 5;

    CodingNinjaSolution s;
    bool result = s.carPooling(trips, capacity);

    // Print result
    if (result) {
        cout << "It is possible to transport all passengers within the given capacity." << endl;
    } else {
        cout << "It is not possible to transport all passengers within the given capacity." << endl;
    }
    return 0;
}

Output

Output

Java Implementation

public class CodingNinjaSolution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] prefixSum = new int[1001]; // 1001 is the maximum possible end location

        // Calculate the prefix sum of passengers at each location
        for (int[] trip : trips) {
            prefixSum[trip[1]] += trip[0];
            prefixSum[trip[2]] -= trip[0];
        }

        // Iterate over the prefix sum and check capacity at each location
        for (int i = 0; i < prefixSum.length; i++) {
            capacity -= prefixSum[i];
            if (capacity < 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        // Hardcoded input
        int[][] trips = {{1,1,3}, {2,2,6}, {3,5,9}};
        int capacity = 5;

        CodingNinjaSolution s = new CodingNinjaSolution();
        boolean result = s.carPooling(trips, capacity);

        // Print result
        if (result) {
            System.out.println("It is possible to transport all passengers within the given capacity.");
        } else {
            System.out.println("It is not possible to transport all passengers within the given capacity.");
        }
    }
}

Output

Output

Explanation

In this method, we first create a frequency array freq of size 1001 (since the maximum value of any location in the problem is 1000), and initialize all elements of the array to 0. Then, we iterate over the trips array, add the number of passengers to freq[startLocation], and subtract the number of passengers from freq[endLocation]. This process updates the frequency array to keep track of the number of passengers at each location.

After updating the frequency array, we iterate over the array and calculate the prefix sum prefix[i] = prefix[i-1] + freq[i] for each index i. This prefix sum array keeps track of the number of passengers up to each location.

Finally, we iterate over the prefix array and check if the number of passengers at any location exceeds the given capacity. If so, we return false, indicating that it is not possible to transport all passengers within the given capacity. Otherwise, we return true.

Complexity

Time complexity

O(n), where n is the number of trips.

Reason: Since we iterate over the trips array, the prefix array, and the freq array once. So complexity is O(n). Therefore, this method is more efficient than the priority queue method, which has a time complexity of O(n log n) due to the use of a priority queue.

Space complexity

O(1)

Reason: we create a frequency array freq of size 1001 to keep track of the number of passengers at each location. We also create a prefix sum array prefix of the same size to keep track of the total number of passengers up to each location. Both arrays have a constant size of 1001, regardless of the number of trips or the capacity. Therefore, the space complexity of this method is O(1).

Frequently Asked Questions

What is pre-computation in Problem-solving?

We find some important points and use them in solving the questions.

What are some applications of the carpooling problem in real-world scenarios?

The carpooling problem has applications in various real-world scenarios, such as ride-sharing platforms, transportation planning, and public transit optimisation. It is also relevant to the management of corporate carpooling programs, school transportation systems, and on-demand transportation services.

How does a Priority Queue differ from a regular Queue?

The main difference between a Priority Queue and a regular Queue is that a Priority Queue prioritizes elements based on their priority value, while a regular Queue serves elements in the order they were added. In a Priority Queue, elements with higher priority are served before elements with lower priority, regardless of the order in which they were added.

What is the Time Complexity of the Naive approach?

Time Complexity is O(N^2), and Space Complexity is O(N).

What operations can be performed on a Priority Queue?

The most common operations that can be performed on a Priority Queue include inserting an element with a priority value, removing the element with the highest priority, and peeking at the element with the highest priority without removing it. Some Priority Queue implementations may also support updating the priority of an element and merging two Priority Queues.

Conclusion

In this, we learn that one of the concepts used for solving the problem is pre-computation and how to apply that in solving the problem. For taking the example of it, we can see in the problem that we need to compare with the capacity of the person currently in the car, so for the sake of convenience for repeated calculation, we directly store the current people in the car for particular kilometres in the form of an array, which also helps to optimise the code by reducing the steps of calculation with reduced Time Complexity, from their idea of Pre-computation developed. 

In general, we apply it when we perform the same task. For the next part, we also need to calculate the previous, so we do Pre-computation, which often reduces the time of calculation and complexity of the problem of Data Structure.

Check out this problem - Queue Implementation

The suggested list of practice problems to enhance your coding skills.

This blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem, and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Enrol in our coursesrefer to the test series and problems available and look at the interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Divide the Chocolate
Next article
Sort an Array of 0s,1s and 2s
Live masterclass