Problem Overview

You are given:

• An integer capacity

• A list of trips

Each trip is represented as:

[numPassengers, from, to]

Meaning:

• numPassengers passengers enter the car at location from

• They leave the car at location to

The car only moves east, so locations are processed from left to right.

Your task is to determine:

Can the car complete all trips without exceeding its capacity at any point?

This problem is popular in interviews because it tests:

• Prefix Sum

• Difference Array Technique

• Sweep Line Thinking

• Event-based processing

• Optimization over simulation

Example

Input:

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

Trip 1:

• Pick up 2 passengers at location 1

• Drop them off at location 5

Trip 2:

• Pick up 3 passengers at location 3

• Drop them off at location 7

Passenger Timeline

At location 3:

5 > capacity

So the answer is:

false

Approach 1: Direct Simulation

Idea

We could simulate every location manually.

For every kilometer:

• Check which passengers enter

• Check which passengers leave

• Track current passengers

Disadvantages

If locations become large:

0 <= location <= 1000

the repeated checking becomes inefficient.

A more elegant solution exists using a Difference Array.

Best Approach: Difference Array + Prefix Sum

Core Observation

Instead of simulating every trip continuously,

we only care about two events:

• Where passengers enter

• Where passengers leave

This is the perfect use case for a Difference Array.

Understanding the Difference Array

We create an array:

diff[i]

Where:

• Positive value → passengers enter

• Negative value → passengers leave

For every trip:

[numPassengers, from, to]

We do:

diff[from] += numPassengers
diff[to] -= numPassengers

Why?

Because:

• At from, passengers are added

• At to, passengers are removed

Then later, we compute a running prefix sum to know:

How many passengers are currently inside the car.

Step-by-Step Example

Input

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

Step 1: Build Difference Array

Initially:

diff = [0,0,0,0,0,0,0,0]

Process first trip:

[2,1,5]

Update:

diff[1] += 2
diff[5] -= 2

Now:

[0,2,0,0,0,-2,0,0]

Process second trip:

[3,3,7]

Update:

diff[3] += 3
diff[7] -= 3

Final diff array:

[0,2,0,3,0,-2,0,-3]

Step 2: Compute Running Passengers

We compute prefix sums.

Location 0:

0

Location 1:

0 + 2 = 2

Location 2:

2

Location 3:

2 + 3 = 5

Now:

5 > capacity

So we immediately return:

false

Why This Works

The major insight is:

Instead of tracking every passenger continuously,

we only record changes at specific locations.

Then the prefix sum reconstructs:

current passengers at every point

This transforms the problem into a clean linear scan.

Time and Space Complexity

Time Complexity

O(n + 1000)

Where:

• n = number of trips

• 1000 = maximum possible location

Essentially linear.

Space Complexity

O(1000)

For the difference array.

Final Code (Optimized)

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

        for (auto &trip : trips) {

            int passengers = trip[0];
            int from = trip[1];
            int to = trip[2];

            diff[from] += passengers;
            diff[to] -= passengers;
        }

        int currentPassengers = 0;

        for (int i = 0; i <= 1000; i++) {

            currentPassengers += diff[i];

            if (currentPassengers > capacity)
                return false;
        }

        return true;
    }
};

Key Interview Insight

The hardest part of this problem is recognizing that:

We do not need to simulate the entire journey.

We only need to process passenger changes at pickup and drop-off points.

That leads directly to:

• Difference Array

• Prefix Sum

• Sweep Line Technique

This converts the problem into:

• Simple updates

• One linear traversal

• Efficient event processing

This is a classic interval-processing optimization problem frequently asked in interviews.