< Back




1094. Car Pooling

Difference array or bucket sorting question, very similar to prefix sum questions. This question
format usually provides us with an array of unsorted sets, we're given a start and end point for
some particular value and asked to find the maximum or find something that violates some constraint.

Bucket sorting involves roughly knowing the size of the input and, in this case, we know that the
furthest destination is 1000, so we can create a difference table of 1001 - making our space
complexity O(1). Otherwise, we would have to find the max destiniation, which would be O(m + n)
time.

With bucket sorting, we place start and end times in buckets, the indices they correspond to in our
difference array. We place passengers at the start time bucket, and we remove passengers at the end
time bucket.

Now, when we traverse from 0 to the end of the diff array, we maintain a prefix sum of all the
passengers who have entered and exited the vehicle. Passengers will enter the vehicle during their
start time, and exit the vehicle during their end time - because we've accounted for this with
bucket sort.

If we ever have too many passengers for the capacity of the vehicle, we'll violate the constaint
of currPassengers > capacity, and we return False. Otherwise, we'll return True.

The solution is as follows:


  class Solution:
      def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
          diff = [0] * 1001

          for numPassengers, start, end in trips:
              diff[start] += numPassengers
              diff[end] -= numPassengers

          currPassengers = 0

          for d in diff:
              currPassengers += d

              if currPassengers > capacity:
                  return False

          return True


_ Time Complexity:

  O(max(n, 1001)) - Where n is the number of trips, we can either spend most of our time processing
  the trips input, or if it's smaller than our diff array, we can process it in constant time.

_ Space Complexity:

  O(1) - Our diff array will always be size O(1001) - constant.