1094. Car Pooling LeetCode Solution

In this guide, you will get 1094. Car Pooling LeetCode Solution with the best time and space complexity. The solution to Car Pooling problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Car Pooling solution in C++
Car Pooling solution in Java
Car Pooling solution in Python
Additional Resources

1094. Car Pooling LeetCode Solution image

Problem Statement of Car Pooling

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

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1094. Car Pooling LeetCode Solution in C++

class Solution {
 public:
  bool carPooling(vector<vector<int>>& trips, int capacity) {
    int currentPassengers = 0;
    map<int, int> line;

    for (const vector<int>& trip : trips) {
      const int nPassengers = trip[0];
      const int start = trip[1];
      const int end = trip[2];
      line[start] += nPassengers;
      line[end] -= nPassengers;
    }

    for (const auto [_, passengerChange] : line) {
      currentPassengers += passengerChange;
      if (currentPassengers > capacity)
        return false;
    }

    return true;
  }
};
/* code provided by PROGIEZ */

1094. Car Pooling LeetCode Solution in Java

class Solution {
  public boolean carPooling(int[][] trips, int capacity) {
    int currentPassengers = 0;
    Map<Integer, Integer> line = new TreeMap<>();

    for (int[] trip : trips) {
      final int nPassengers = trip[0];
      final int start = trip[1];
      final int end = trip[2];
      line.merge(start, nPassengers, Integer::sum);
      line.merge(end, -nPassengers, Integer::sum);
    }

    for (final int passengerChange : line.values()) {
      currentPassengers += passengerChange;
      if (currentPassengers > capacity)
        return false;
    }

    return true;
  }
}
// code provided by PROGIEZ

1094. Car Pooling LeetCode Solution in Python

class Solution {
 public:
  bool carPooling(vector<vector<int>>& trips, int capacity) {
    int currentPassengers = 0;
    vector<int> line(1001);

    for (const vector<int>& trip : trips) {
      const int nPassengers = trip[0];
      const int start = trip[1];
      const int end = trip[2];
      line[start] += nPassengers;
      line[end] -= nPassengers;
    }

    for (const int passengerChange : line) {
      currentPassengers += passengerChange;
      if (currentPassengers > capacity)
        return false;
    }

    return true;
  }
};
 # code by PROGIEZ