Frequently Asked — This problem has been reported multiple times in recent Amazon interviews. Prioritize this during revision.

Car Pooling

Problem Statement

You are driving a vehicle with capacity seats. You are given a list of trips where trips[i] = [numPassengers, from, to]. The i-th trip picks up numPassengers passengers at location from and drops them off at location to. Return true if it is possible to pick up and drop off all passengers without exceeding the vehicle capacity at any point.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation: At location 3, you have 2 (from trip 0) + 3 (from trip 1) = 5 passengers, 
but capacity is 4.

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Explanation: Peak is 5 at locations 3-4, which equals capacity.

Constraints:

• 1 <= trips.length <= 1000
• 1 <= numPassengers <= 100
• 0 <= from < to <= 1000

Difficulty: Medium (LC 1094)

---

Pattern Recognition

• What is the input structure? A list of intervals (start, end) with associated weights (passengers).
• What are we optimizing? Checking if the maximum concurrent weight ever exceeds a capacity.
• What pattern does this fit? Sweep Line / Difference Array. Record "+passengers" at from and "-passengers" at to, then sweep through to find the peak.
• Why does this pattern fit? This is a classic interval overlap problem with weights. The difference array technique efficiently computes the aggregate value at every point by only recording changes at interval boundaries.

---

Approach

Brute Force — Simulate Each Location

For each location 0 to 1000, count how many passengers are in the car.

for loc in 0..1000:
    count = 0
    for trip in trips:
        if trip.from <= loc < trip.to:
            count += trip.passengers
    if count > capacity: return false
return true

Time: O(1001 * n) where n is the number of trips. With n=1000, this is ~10^6 — actually fine, but inelegant. Space: O(1). Why insufficient: Not scalable. If locations could be up to 10^9, this approach fails.

Optimal — Difference Array

Key Insight: Instead of checking every location, record only the changes. At from, passengers get on (+). At to, passengers get off (-). Sweep through the changes in order and track the running total. If it ever exceeds capacity, return false.

Step-by-step:

1. Create a difference array of size 1001 (max location + 1).
2. For each trip [passengers, from, to]:
   • diff[from] += passengers
   • diff[to] -= passengers
3. Sweep through the array, accumulating the running sum.
4. If the running sum ever exceeds capacity, return false.
5. Otherwise, return true.

function carPooling(trips, capacity):
    diff = [0] * 1001
    for passengers, from, to in trips:
        diff[from] += passengers
        diff[to] -= passengers
    running = 0
    for i in 0..1000:
        running += diff[i]
        if running > capacity: return false
    return true

Time: O(n + max_location). With max_location = 1000, this is O(n + 1000) = O(n). Space: O(max_location) = O(1) since max_location is bounded by 1000.

Alternative — Event-Based (Sort Events)

If locations could be large (up to 10^9), use events instead of a fixed array:

1. Create events: (from, +passengers) and (to, -passengers) for each trip.
2. Sort events by location. For ties, process drop-offs before pickups (to avoid false capacity violations).
3. Sweep through events, tracking running passenger count.

Time: O(n log n) for sorting. Space: O(n) for events.

---

Walkthrough

trips = [[2,1,5], [3,3,7], [1,4,6]], capacity = 5

Step 1 — Build difference array:

Trip	Action	diff changes
[2,1,5]	diff[1] += 2, diff[5] -= 2	diff[1]=2, diff[5]=-2
[3,3,7]	diff[3] += 3, diff[7] -= 3	diff[3]=3, diff[7]=-3
[1,4,6]	diff[4] += 1, diff[6] -= 1	diff[4]=1, diff[6]=-1

Relevant diff values: [0, 2, 0, 3, 1, -2, -1, -3]

Step 2 — Sweep:

Location	diff[loc]	Running total	Exceeds 5?
0	0	0	No
1	2	2	No
2	0	2	No
3	3	5	No
4	1	6	Yes!

Answer: false — at location 4, there are 6 passengers (2 from trip 0, 3 from trip 1, 1 from trip 2) but capacity is 5.

---

Implementation

Difference Array Approach

TypeScript

function carPooling(trips: number[][], capacity: number): boolean {
    // Difference array — locations go from 0 to 1000
    const diff = new Array(1001).fill(0);

    for (const [passengers, start, end] of trips) {
        diff[start] += passengers; // Passengers board
        diff[end] -= passengers;   // Passengers exit (note: they're gone AT 'end')
    }

    // Sweep through all locations
    let running = 0;
    for (let i = 0; i <= 1000; i++) {
        running += diff[i];
        if (running > capacity) return false;
    }

    return true;
}

C++

bool carPooling(vector<vector<int>>& trips, int capacity) {
    // Difference array — locations go from 0 to 1000
    int diff[1001] = {};

    for (auto& trip : trips) {
        int passengers = trip[0], start = trip[1], end = trip[2];
        diff[start] += passengers; // Passengers board
        diff[end] -= passengers;   // Passengers exit (note: they're gone AT 'end')
    }

    // Sweep through all locations
    int running = 0;
    for (int i = 0; i <= 1000; i++) {
        running += diff[i];
        if (running > capacity) return false;
    }

    return true;
}

Event-Based Approach (works for large coordinates)

TypeScript

function carPoolingEvents(trips: number[][], capacity: number): boolean {
    const events: [number, number][] = [];

    for (const [passengers, start, end] of trips) {
        events.push([start, passengers]);   // Board
        events.push([end, -passengers]);    // Exit
    }

    // Sort by location; for same location, process exits before boards
    // (negative values sort before positive, which is exactly what we want)
    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    let running = 0;
    for (const [, change] of events) {
        running += change;
        if (running > capacity) return false;
    }

    return true;
}

C++

bool carPoolingEvents(vector<vector<int>>& trips, int capacity) {
    vector<pair<int, int>> events;

    for (auto& trip : trips) {
        int passengers = trip[0], start = trip[1], end = trip[2];
        events.push_back({start, passengers});   // Board
        events.push_back({end, -passengers});     // Exit
    }

    // Sort by location; for same location, process exits before boards
    // (negative values sort before positive — pair comparison handles this)
    sort(events.begin(), events.end());

    int running = 0;
    for (auto& [loc, change] : events) {
        running += change;
        if (running > capacity) return false;
    }

    return true;
}

Watch out:

1. Passengers exit AT to, not after to. The problem says passengers are dropped off at to, meaning at location to they are no longer in the car. So diff[to] -= passengers, not diff[to + 1]. This is confirmed by the constraint from < to.
2. Event ordering at the same location. When a drop-off and pickup happen at the same location, the drop-off should be processed first. In the event-based approach, (-passengers) sorts before (+passengers) at the same location, so this works naturally. The difference array approach handles this implicitly since additions and subtractions at the same index are summed.
3. Off-by-one with the difference array size. Locations go up to 1000, so the array needs 1001 elements (indices 0 through 1000).

---

Complexity Analysis

	Time	Space
Brute Force (Simulate)	O(max_loc * n)	O(1)
Difference Array	O(n + max_loc)	O(max_loc)
Event-Based (Sort)	O(n log n)	O(n)

Bottleneck: The difference array approach is O(n + 1000) which is effectively O(n) since 1000 is a constant. For the event-based approach, the O(n log n) sorting dominates. Both are efficient for the given constraints. The difference array is simpler when the coordinate range is small and bounded.

---

Edge Cases

1. Single trip — Return passengers <= capacity.
2. No overlapping trips — The maximum concurrent passengers equals the max of individual trips.
3. All trips start and end at the same locations — Sum of all passengers vs capacity.
4. Capacity = 1, all trips have 1 passenger — Reduces to checking if any trips overlap.
5. Trip from location 0 — Ensure the difference array handles index 0 correctly.
6. Maximum constraints (1000 trips, locations up to 1000) — The difference array handles this in O(2000) which is instant.

---

Related Problems

• LC 253 — Meeting Rooms II — Same sweep line pattern: find the maximum number of overlapping intervals.
• LC 732 — My Calendar III — Dynamically track the maximum overlap count with events. Same event-based sweep idea.
• LC 370 — Range Addition — Direct application of the difference array technique on an array.
• LC 1109 — Corporate Flight Bookings — Identical to car pooling: difference array over a range with values.

---

What is Expected at Each Level

Junior: Simulate each location and count passengers. Recognize that the brute force is O(n * max_loc) and may be slow. With guidance, learn the difference array technique.

Mid-level: Immediately identify this as a sweep line / difference array problem. Write clean code. Discuss the event-based alternative for larger coordinate ranges. Handle the drop-off semantics correctly.

Senior: Solve in under 5 minutes with the difference array. Discuss when to use difference arrays vs sorted events vs segment trees. Extend to: "What if trips can be cancelled?" (Need a segment tree or re-sweep.) "What if coordinates are up to 10^9?" (Event-based approach.) Connect to real-world capacity planning systems.