Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Thursday, June 4

    Car Pooling

    Updated: Algorithms 3 Comments1 Min Readdevangini123By

    Problem Statement:

    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 <= 1000
    • trips[i].length == 3
    • 1 <= numPassengersi <= 100
    • 0 <= fromi < toi <= 1000
    • 1 <= capacity <= 105

    Approach:

    • Create an array loc[1001] to track passenger changes at each location.
      • At pickup point from, add +passengers.
      • At drop point to, subtract -passengers.
    • Traverse loc while maintaining usedCapacity.
      • Keep adding changes at each location.
      • If usedCapacity ever exceeds carCapacity, return false.
    • If the loop completes without exceeding capacity, return true.

    Time & Space Complexity:

    Time Complexity: O(n)

    Space Complexity: O(1)

    Dry Run

    Input: arr = [[2,1,5],[3,3,7]], carCapacity = 4

    
Step 0: Start Function: carPooling(arr, carCapacity)
arr = [[2,1,5], [3,3,7]]
carCapacity = 4
loc = Array(1001).fill(0)
usedCapacity = 0

Step 1: Process trips
Iteration (i = 0): arr[0] = [2,1,5]
- passengers = 2, from = 1, to = 5
- loc[1] = loc[1] + 2 → loc[1] = 2
- loc[5] = loc[5] - 2 → loc[5] = -2

Iteration (i = 1): arr[1] = [3,3,7]
- passengers = 3, from = 3, to = 7
- loc[3] = loc[3] + 3 → loc[3] = 3
- loc[7] = loc[7] - 3 → loc[7] = -3

Final loc changes (only relevant indices):
loc[1] = 2, loc[3] = 3, loc[5] = -2, loc[7] = -3

Step 2: Iterate over loc to check capacity
i = 0: usedCapacity = 0 + loc[0] = 0  
i = 1: usedCapacity = 0 + 2 = 2 → (≤ 4, OK)  
i = 2: usedCapacity = 2 + 0 = 2 → (≤ 4, OK)  
i = 3: usedCapacity = 2 + 3 = 5 → (> 4, exceeds capacity)  

Condition triggered → return false

Step 3: End
Function returns false because at i = 3, usedCapacity exceeded carCapacity

    Output: false

    
var carPooling = function(trips, carCapacity) {
    let loc = Array(1001).fill(0);
    for (let i = 0; i < trips.length; i++) {
        let [passengers, from, to] = trips[i];
        loc[from] += passengers;   // Pick up passengers
        loc[to] -= passengers;     // Drop off passengers
    }
    let usedCapacity = 0;
    for (let i = 0; i < 1001; i++) {
        usedCapacity += loc[i];
        if (usedCapacity > carCapacity) {
            return false; 
        }
    }
    return true; 
};

    
def carPooling(trips, capacity):
    loc = [0] * 1001
    for passengers, frm, to in trips:
        loc[frm] += passengers
        loc[to] -= passengers

    used_capacity = 0
    for x in loc:
        used_capacity += x
        if used_capacity > capacity:
            return False
    return True
      
    
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] loc = new int[1001];
        for (int i = 0; i < trips.length; i++) {
            int passengers = trips[i][0];
            int from = trips[i][1];
            int to = trips[i][2];
            loc[from] += passengers;
            loc[to] -= passengers;
        }
        int usedCapacity = 0;
        for (int i = 0; i < loc.length; i++) {
            usedCapacity += loc[i];
            if (usedCapacity > capacity) return false;
        }
        return true;
    }
}
    
    

#include <vector>
using namespace std;

class Solution {
public:
    bool carPooling(vector>& trips, int capacity) {
        vector loc(1001, 0);
        for (const auto &t : trips) {
            int passengers = t[0];
            int from = t[1];
            int to = t[2];
            loc[from] += passengers;
            loc[to] -= passengers;
        }
        int usedCapacity = 0;
        for (int x : loc) {
            usedCapacity += x;
            if (usedCapacity > capacity) return false;
        }
        return true;
    }
};

    
#include <stdbool.h>
#include <string.h>
#include <stddef.h>

bool carPooling(int trips[][3], size_t tripsSize, int capacity) {
    int loc[1001];
    memset(loc, 0, sizeof(loc));
    for (size_t i = 0; i < tripsSize; ++i) {
        int passengers = trips[i][0];
        int from = trips[i][1];
        int to = trips[i][2];
        loc[from] += passengers;
        loc[to] -= passengers;
    }
    int usedCapacity = 0;
    for (int i = 0; i < 1001; ++i) {
        usedCapacity += loc[i];
        if (usedCapacity > capacity) return false;
    }
    return true;
}
 
    
using System;
public class Solution {
    public bool CarPooling(int[][] trips, int capacity) {
        int[] loc = new int[1001];
        for (int i = 0; i < trips.Length; i++) {
            int passengers = trips[i][0];
            int from = trips[i][1];
            int to = trips[i][2];
            loc[from] += passengers;
            loc[to] -= passengers;
        }

        int usedCapacity = 0;
        for (int i = 0; i < loc.Length; i++) {
            usedCapacity += loc[i];
            if (usedCapacity > capacity) return false;
        }
        return true;
    }
}

    Keep Reading

    View 3 Comments

    3 Comments

    Leave A Reply

    Demo

    Courses

    Community

    Contact Us