Car Pooling

Yogesh Kumar
Last Updated: May 18, 2022
Difficulty Level :
HARD

Introduction

Today’s problem, i.e., –Car Pooling,” is highly asked in product-based companies like Amazon, Google, and Microsoft.

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.

Problem Statement

There is a car with empty capacity seats. The vehicle only drives east (i.e., it cannot turn around and drive west). You are given the integer capacity, and an array of trips where trip[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.

Explanation

In the above problem statement, initially, a car has an empty capacity. A vehicle going in one direction can't be reversed, i.e., only directed in the east direction can come in the west direction. Several hall points in the form of the array are given for a number of people, the start point, and the endpoint for the complete long drive journey with a vehicle’s capacity, which is possible for the car. trip[i]= [number_of_person_i, start_point_i, end_point_i] .

Now we have to check if all passengers can be picked up and dropped off without exceeding the capacity value at any point in time; if we make it possible to do a task without capacity exceeding, we have to return true; we have to return false.

 

Let's take an example to understand the problem in a more clear manner for better understanding.

  1. Input :  trips= [ [ 3 , 2 , 7 ] , [ 3 , 7 , 9 ] , [ 8 , 3 ,9 ] ]   capacity =11

               Output: True

3 person

  (2)X--------------------------------------X(7)   (a)

8 person

  (3)X-------------------------------------------X(9)  (b)

3 person 

   (7)X-----------X(9) (c)

 

  1. Now their start and endpoint are 2 and 7, and the person traveling is 3
  2. Now for the next part, at 3 (+8) persons, more gets added up than 3+8=11<=capacity.
  3. Now for next at point 7 (-3) and (+3), so again we have number 11, so it’s working fine.
  4. Hence we complete the whole journey with constraints at each stage capacity <=given capacity.

 

2. Input: trips [ [ 2 , 1 , 5 ] , [ 3 , 3 , 7 ] ]  capacity : 4

    Output : False

 

2 person

(1)X---------------------------X(5) (a)

3 person

(3)X-------------------------------X(7) (b)

  1. We start with initial point 1 and endpoint 5 with 2 persons <=capacity.
  2. For the next part, 3 people were added before leaving the 2 people at 3 km, so 5, not <=capacity, which violates the condition; hence we have to return false.

Solution-1(Naive Approach)

In this approach, we, understanding the problem with the example above, if we somehow know the person who is still on the particular distance and compares with the capacity of the Vehicle, then we run it over the journey and check its given capacity with present value willing to run it for the N times, by naive approach for the N trip.

Algorithm

  1. Declare an array that stores the people who are still present in the car for the journey.
  2. Now run a loop for the trip length as to how many sub-trip are present in the trips list.
  3. Iterate over the sub-trips and compute the number of people currently in the car with a total capacity.
  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 and return false.

Code

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int [] arr=new int[1000];
        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){
                              return false;
                      }
              }
        }
        return true;
    }
}

 

Input:

trips = [[2,1,5],[3,3,7]], capacity = 4

Output:

false

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.

Solution-2(Optimized in pre-computation)

In this approach, we try to optimize the solution-1 code from O(N^2) to O(N).

In this approach, we use the entry and exit point of distance for the number of people inserted in the car, so on moving forward, if we get a count of 0 for covering the entire, when we return true if it becomes less than 0, then we return false.

Algorithm

  1. Declare an array for storing the number of people entering and leaving at the endpoint or start point.
  2. All arrays are declared to have an initial value of 0.
  3. Now iterate a loop to store the person number in an array as in step-1.
  4. Now run another loop and start diminishing the person from the capacity as to the endpoint. For that, we check the capacity size as if it goes less than 0; then we have to return false else, we iterate and loop entirely, then we return true.
  5. The second Loop is the substrate from capacity as, if it does not come to less than 0, then we have the required space in the car otherwise, <0 means it will overflow.

Code

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int [] person=new int[10001];
        for(int t[]:trips){
                person[t[1]]+=t[0];
                person[t[2]]-=t[0];
        }
        for(int num:person){
                capacity-=num;
                if(capacity<0){
                        return false;
                }
        }
        return true;
    }
}

 

Input:

trips = [[2,1,5],[3,3,7]], capacity = 4

Output:

false

 

Complexity Analysis

Taking about the Time complexity of the code, we can see that in the form of the array, we are storing the endpoint of entering and leaving the person, O(N), and another loop in linear time in O(N); these two are separate, so Time Complexity O(N) and Space Complexity is also O(N) for extra array declaration.

Frequently Asked Questions

What is pre-computation in Problem solving?

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

What is the Time Complexity of the Naive approach?

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

What is Time Complexity and Space Complexity for the Optimized approach?

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

 

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 kilometers in the form of an array, which also helps to optimize the code by reducing the steps of calculation with reduced Time Complexity, from their idea of Pre-computation developed. In general, we apply it where 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.

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

I hope that 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 CodeStudio. Enroll in our courses, refer 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!!

Was this article helpful ?
0 upvotes