1094. Car Pooling

📝 Problem Details

• Title: 1094. Car Pooling
• Link: https://leetcode.com/problems/car-pooling/
• Difficulty: Medium
• Tags/Categories: Hashmap Arrays

💭What Were My Initial Thoughts?

- track the passenger changes (pickups and dropoffs) at various points along the trip
- verify if at any point the number of passengers exceeds the cars capacity

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- **Difference Array Concept**:
    - Instead of directly iterating over all possible points along the route, we use a map (`diff`) to record the change in the number of passengers at specific locations.
    - A positive value at a location means passengers are being picked up, and a negative value means passengers are being dropped off.

- **Build the Difference Map**:
    - For each trip in `trips`:
        - Add the number of passengers to the start location (`diff[start] += numPassengers`).
        - Subtract the same number of passengers from the end location (`diff[end] -= numPassengers`).
    - This captures the net change in passengers at each relevant location.

- **Simulate Passenger Flow**:
    - Traverse the difference map in **ascending order of locations**.
    - Maintain a running total (`currentPassengers`) to represent the number of passengers in the car.
    - If at any point `currentPassengers > capacity`, return `false`.

- **Output the Result**:
    - If you traverse all locations without exceeding the capacity, return `true`.

⌛ Complexity Analysis

Time Complexity: O(n) to build the hashmap
Space Complexity: O(n) to store the map

💻 Implementation of Solution

bool carPooling(vector<vector<int>>& trips, int capacity) {
    map<int, int> diff; // Difference array
 
    // Build the difference map
    for (auto &trip : trips) {
        int numPassengers = trip[0];
        int start = trip[1];
        int end   = trip[2];
 
        diff[start] += numPassengers; // Picking up passengers
        diff[end]   -= numPassengers; // Dropping off passengers
    }
 
    // Track current number of passengers
    int currentPassengers = 0;
 
    // Traverse locations in ascending order
    for (auto &kv : diff) {
        currentPassengers += kv.second;  // Update current passengers
        if (currentPassengers > capacity) {
            return false; // Capacity exceeded
        }
    }
 
    return true; // Capacity never exceeded
}