Skip to main content

1094. Car Pooling

mediumAsked at Airbnb

Check whether a shared vehicle ever exceeds capacity across multiple pickup-dropoff trips — Airbnb's Trips team applies this interval-difference-array pattern to validate that shared shuttles to airports never overbook across overlapping passenger legs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is a car with capacity empty seats. Given an array trips where trips[i] = [numPassengers_i, from_i, to_i], return true if it is possible to pick up and drop off all passengers for all trips, or false otherwise.

Constraints

  • 1 <= trips.length <= 1000
  • trips[i].length == 3
  • 1 <= numPassengers_i <= 100
  • 0 <= from_i < to_i <= 1000
  • 1 <= capacity <= 10^5

Examples

Example 1

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

Explanation: At stop 3 both trips overlap: 2+3=5 > 4.

Example 2

Input
trips = [[2,1,5],[3,3,7]], capacity = 5
Output
true

Approaches

1. Sort events (sweep line)

Convert each trip into a +passengers pickup event and a -passengers dropoff event. Sort by position, then sweep to track occupancy at each stop.

Time
O(n log n)
Space
O(n)
function carPooling(trips, capacity) {
  const events = [];
  for (const [num, from, to] of trips) {
    events.push([from, num], [to, -num]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let current = 0;
  for (const [, delta] of events) {
    current += delta;
    if (current > capacity) return false;
  }
  return true;
}

Tradeoff:

2. Difference array (O(1001) positions)

Use a fixed-size difference array indexed by stop position. Add passengers at from, subtract at to. Prefix-sum the array and check if any position exceeds capacity.

Time
O(n + max_stop)
Space
O(max_stop)
function carPooling(trips, capacity) {
  const stops = new Array(1001).fill(0);
  for (const [num, from, to] of trips) {
    stops[from] += num;
    stops[to] -= num;
  }
  let current = 0;
  for (const delta of stops) {
    current += delta;
    if (current > capacity) return false;
  }
  return true;
}

Tradeoff:

Airbnb-specific tips

Airbnb frames this as a shared-shuttle validation problem: 'Does our airport shuttle ever get overloaded?' The difference array approach is the cleanest for bounded stop ranges and is the expected answer at Airbnb. Interviewers then ask: 'What if stop values could be up to 10^9?' — pivot to the event-sort approach and explain why the difference array would waste memory. Show both and let the constraints drive the choice.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Car Pooling and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →