Difficulty: Medium
Category: Array, Sorting, Simulation
Companies: Amazon, Google, Microsoft, Uber

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] = [numPassengers, from, to] indicates that the i-th trip has numPassengers passengers and the locations to pick them up and drop them off are from and to 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.

Examples

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation: 
- Trip 1: Pick up 2 passengers at location 1, drop off at location 5
- Trip 2: Pick up 3 passengers at location 3, drop off at location 5
- At location 3, we have 2 + 3 = 5 passengers, which exceeds capacity (4)

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Explanation: 
- Trip 1: Pick up 2 passengers at location 1, drop off at location 5
- Trip 2: Pick up 3 passengers at location 3, drop off at location 5
- At location 3, we have 2 + 3 = 5 passengers, which equals capacity (5)

Constraints

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengers <= 100
  • 0 <= from < to <= 1000

Solution Approaches

Key Insight: Use a bucket array to track passenger changes at each timestamp. Add passengers at pickup locations and subtract at drop-off locations.

Algorithm:

  1. Create a timestamp array of size 1001 (since locations are 0-1000)
  2. For each trip, add passengers at pickup location and subtract at drop-off location
  3. Iterate through timestamps and track cumulative passengers
  4. Return false if capacity is exceeded at any point

Time Complexity: O(n + 1001) = O(n)
Space Complexity: O(1001) = O(1)

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

        # Build difference array
        for trip in trips:
            timestamp[trip[1]] += trip[0]  # pick up
            timestamp[trip[2]] -= trip[0]  # drop off

        usedCapacity = 0

        # Sweep line (prefix sum)
        for number in timestamp:
            usedCapacity += number
            if usedCapacity > capacity:
                return False

        return True

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: Difficulty:** Medium

How the code works: Difficulty: Medium Category: Array, Sorting, Simulation

  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input trips = [[2,1,5],[3,3,7]], capacity = 4, expected output false:

  • Trip 1: Pick up 2 passengers at location 1, drop off at location 5
  • Trip 2: Pick up 3 passengers at location 3, drop off at location 5
  • At location 3, we have 2 + 3 = 5 passengers, which exceeds capacity (4)

    Implementation Details

Bucket Sort Technique

class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        events = []  # (location, passenger_change)

        # Step 1: build events
        for trip in trips:
            events.append((trip[1], trip[0]))   # pickup
            events.append((trip[2], -trip[0]))  # dropoff

        # Step 2: sort once
        events.sort()

        # Step 3: sweep line
        usedCapacity = 0
        for location, change in events:
            usedCapacity += change
            if usedCapacity > capacity:
                return False

        return True

Event Processing

import heapq

class Solution:
    def carPooling(self, trips: list[list[int]], capacity: int) -> bool:
        trips.sort(key=lambda x: x[1])  # sort by pickup

        pq = []  # (dropoff, passengers)
        usedCapacity = 0

        for passengers, pickup, dropoff in trips:

            # Step 1: drop off passengers who already finished
            while pq and pq[0][0] <= pickup:
                usedCapacity -= heapq.heappop(pq)[1]

            # Step 2: pick up new passengers
            usedCapacity += passengers

            # Step 3: check capacity
            if usedCapacity > capacity:
                return False

            # Step 4: add this trip to heap
            heapq.heappush(pq, (dropoff, passengers))

        return True

Edge Cases

  1. Single Trip: [[1,0,1]] with capacity 1 → true
  2. No Trips: [] with any capacity → true
  3. Exact Capacity: Passengers exactly equal capacity → true
  4. Overlapping Trips: Multiple trips at same location → check total

Follow-up Questions

  • What if locations could be very large (up to 10^9)?
  • How would you handle multiple cars?
  • What if passengers could be picked up and dropped off at the same location?
  • How would you optimize for very large numbers of trips?

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Optimization Techniques

  1. Bucket Sort: Use array indexing for small ranges
  2. Event-Based Processing: Treat state changes as events
  3. Early Termination: Stop processing when constraint violated
  4. Space Optimization: Use fixed-size arrays when possible

Code Quality Notes

  1. Readability: Bucket sort approach is most intuitive
  2. Performance: O(n) time complexity is optimal
  3. Scalability: Sorting approach works for any range
  4. Robustness: All approaches handle edge cases correctly

Key Takeaways

  • Pattern: Prefix sum (this problem)
  • Difficulty:** Medium
  • Category:** Array, Sorting, Simulation

References

Template Reference

Thinking Process

Difficulty: Medium

Category: Array, Sorting, Simulation

  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants