310. Car Pooling

🔗 LeetCode Problem: 1094. Car Pooling
📊 Difficulty: Medium
🏷️ Topics: Array, Sorting, Heap (Priority Queue), Prefix Sum, Simulation

Problem Statement

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] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi 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.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Explanation: 
At location 1, pick up 2 passengers (total = 2)
At location 3, pick up 3 passengers (total = 5)
Capacity exceeded! (5 > 4)

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Explanation:
At location 1, pick up 2 passengers (total = 2)
At location 3, pick up 3 passengers (total = 5)
At location 5, drop off 2 passengers (total = 3)
At location 7, drop off 3 passengers (total = 0)
Maximum passengers = 5 (at location 3-5)

Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
Explanation:
At location 1, pick up 2 passengers
At location 5, drop off 2, pick up 3 (total = 3)
Never exceeds capacity

Constraints: - 1 <= trips.length <= 1000 - trips[i].length == 3 - 1 <= numPassengersi <= 100 - 0 <= fromi < toi <= 1000 - 1 <= capacity <= 10^5

---

🌳 Visual Understanding - The Car Pooling Problem

Let's Discover This Problem Step by Step:

What's happening?

Think of Uber Pool or shared taxi:
  - Car travels EAST only (can't go back)
  - Passengers get on at "from" location
  - Passengers get off at "to" location
  - Car has limited capacity

Question: Can we handle all trips without exceeding capacity?

Visual Discovery - Example 2:

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

Trip 1: 2 passengers from location 1 to 5
Trip 2: 3 passengers from location 3 to 7

Timeline (driving EAST from location 0):

Location:  0    1    2    3    4    5    6    7
           |    |    |    |    |    |    |    |
Trip 1:         ↑    ═════════════↓
           Pick 2               Drop 2

Trip 2:              ↑    ═════════════════↓
                  Pick 3                 Drop 3

Passengers in car at each location:
  0: 0 passengers
  1: 0 + 2 = 2 (pick up trip 1)
  2: 2
  3: 2 + 3 = 5 (pick up trip 2) ← MAXIMUM!
  4: 5
  5: 5 - 2 = 3 (drop off trip 1)
  6: 3
  7: 3 - 3 = 0 (drop off trip 2)

Maximum passengers: 5
Capacity: 5
Result: 5 <= 5? YES ✓

Visual Discovery - Example 1 (Fails):

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

Same trips, but capacity = 4

Passengers in car:
  Location 3: 2 + 3 = 5 passengers

Maximum passengers: 5
Capacity: 4
Result: 5 > 4? NO ✗

We need 5 seats but only have 4!

The Key Insight:

This is about tracking MAXIMUM CONCURRENT passengers!

Similar to Meeting Rooms II (Problem 301):
  - Meeting Rooms II: Max concurrent meetings
  - Car Pooling: Max concurrent passengers

Difference:
  - Meeting Rooms II: Count meetings
  - Car Pooling: Sum passengers (weighted!)

Same pattern: Track changes over time!

---

🧠 Discovering the Solution - Intuitive Approach

Let's Think Through This:

Question 1: What makes this problem similar to Meeting Rooms II?

Meeting Rooms II:
  Events START and END
  Track maximum concurrent events

Car Pooling:
  Passengers BOARD and ALIGHT
  Track maximum concurrent passengers

Same pattern: EVENTS on a timeline!

Events for car pooling:
  - PICKUP at "from" location
  - DROPOFF at "to" location

Question 2: How to track concurrent passengers?

For each trip [passengers, from, to]:
  Create 2 events:
    - Event 1: +passengers at location "from"
    - Event 2: -passengers at location "to"

Process events in order (west to east):
  Keep running total of passengers
  Track maximum

Example: [[2,1,5], [3,3,7]]
  Events:
    Location 1: +2
    Location 3: +3
    Location 5: -2
    Location 7: -3

  Running total:
    1: 0 + 2 = 2
    3: 2 + 3 = 5 ← MAX
    5: 5 - 2 = 3
    7: 3 - 3 = 0

  Maximum: 5

Question 3: What about same location events?

IMPORTANT: At same location, DROPOFF before PICKUP!

Why?
  Passengers getting OFF free up seats
  Then new passengers can get ON

Example: [[2,1,5], [3,5,7]]
  At location 5:
    Trip 1 drops 2
    Trip 2 picks 3

  Correct order:
    5 - 2 = 3, then 3 + 3 = 6 ✗ WRONG!

  Wait, let me reconsider...

  Actually: Passengers at location 5:
    Before: 2 (from trip 1)
    Drop: 2 passengers
    Pick: 3 passengers
    After: 3 passengers

  Order doesn't matter if we do both!
  But need to track carefully...

Actually, let me think more carefully:

At location 5 with [[2,1,5], [3,5,7]]:
  - Trip 1 passengers get OFF
  - Trip 2 passengers get ON

If we process:
  Option 1: -2 then +3 → 2-2+3 = 3 ✓
  Option 2: +3 then -2 → 2+3-2 = 3 ✓

Same result! But during processing:
  Option 1: peak = 2, then 0, then 3
  Option 2: peak = 2, then 5, then 3

Option 2 shows higher peak!

So DROPOFF must come BEFORE PICKUP at same location!
This avoids artificially inflating the count.

---

🟢 Approach 1: Event-Based (Optimal)

💡 Intuition

Create events for pickups and dropoffs:
  - PICKUP: +passengers at "from"
  - DROPOFF: -passengers at "to"

Sort events by location (and type if same location)

Process events west to east:
  Track running count of passengers
  If ever exceeds capacity → return false

This is the SAME pattern as Meeting Rooms II! 🎯

🎨 Building the Solution

Step 1: Create Events

For each trip [passengers, from, to]:
  Add (from, +passengers)
  Add (to, -passengers)

Sort by location (DROPOFF before PICKUP if same location)

Step 2: Process Events

currentPassengers = 0

For each event in order:
  currentPassengers += event.change

  if currentPassengers > capacity:
    return false

return true

📝 Implementation

import java.util.*;

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // Create events: [location, passengerChange]
        List<int[]> events = new ArrayList<>();

        for (int[] trip : trips) {
            int passengers = trip[0];
            int from = trip[1];
            int to = trip[2];

            // Pickup event: +passengers
            events.add(new int[]{from, passengers});
            // Dropoff event: -passengers
            events.add(new int[]{to, -passengers});
        }

        // Sort events by location
        // If same location: dropoff (-) before pickup (+)
        Collections.sort(events, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];  // Sort by location
            }
            return a[1] - b[1];  // Dropoff (negative) before pickup (positive)
        });

        // Process events
        int currentPassengers = 0;

        for (int[] event : events) {
            currentPassengers += event[1];

            if (currentPassengers > capacity) {
                return false;
            }
        }

        return true;
    }
}

🔍 Complete Dry Run - Example 2

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

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Create events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Trip [2,1,5]:
  Pickup at 1: (1, +2)
  Dropoff at 5: (5, -2)

Trip [3,3,7]:
  Pickup at 3: (3, +3)
  Dropoff at 7: (7, -3)

Events: [(1,+2), (5,-2), (3,+3), (7,-3)]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Sort events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

After sorting by location:
  [(1,+2), (3,+3), (5,-2), (7,-3)]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Process events
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Initialize: currentPassengers = 0

Event (1, +2):
  currentPassengers = 0 + 2 = 2
  2 > 5? NO ✓

Event (3, +3):
  currentPassengers = 2 + 3 = 5
  5 > 5? NO ✓

Event (5, -2):
  currentPassengers = 5 - 2 = 3
  3 > 5? NO ✓

Event (7, -3):
  currentPassengers = 3 - 3 = 0
  0 > 5? NO ✓

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Never exceeded capacity
Return: TRUE ✓

Timeline visualization:
  Loc:  1    3    5    7
  Pass: 2 → 5 → 3 → 0
  Max:      5 (at location 3-5)
  Capacity: 5
  Result: 5 <= 5 ✓

Example with Dropoff Before Pickup

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

Events:
  (1, +2)  - pick 2
  (5, -2)  - drop 2
  (5, +3)  - pick 3

After sorting (dropoff before pickup at same location):
  [(1,+2), (5,-2), (5,+3), (7,-3)]

Process:
  Location 1: 0 + 2 = 2 ✓
  Location 5: 2 - 2 = 0 ✓ (drop first!)
  Location 5: 0 + 3 = 3 ✓ (then pick)
  Location 7: 3 - 3 = 0 ✓

Maximum: 3
Capacity: 3
Result: TRUE ✓

If we did PICKUP before DROPOFF at location 5:
  [(1,+2), (5,+3), (5,-2), (7,-3)]
  Location 5: 2 + 3 = 5 ✗ (would exceed!)

Wrong! That's why dropoff must come first!

📊 Complexity Analysis

Time Complexity: O(n log n)

Create events: O(n)
Sort events: O(n log n)
Process events: O(n)
Total: O(n log n)

Optimal! 🎯

Space Complexity: O(n)

Events list: O(n)

---

🟡 Approach 2: Bucket Array (When Locations Limited)

💡 Intuition

If locations are limited (0 to 1000 in this problem):
  Use array as bucket for each location!

changes[location] = net change in passengers

Then scan array to find maximum

📝 Implementation

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // Locations range from 0 to 1000
        int[] changes = new int[1001];

        // Record passenger changes
        for (int[] trip : trips) {
            int passengers = trip[0];
            int from = trip[1];
            int to = trip[2];

            changes[from] += passengers;   // Pickup
            changes[to] -= passengers;     // Dropoff
        }

        // Scan locations from west to east
        int currentPassengers = 0;

        for (int change : changes) {
            currentPassengers += change;

            if (currentPassengers > capacity) {
                return false;
            }
        }

        return true;
    }
}

📊 Complexity Analysis

Time Complexity: O(n + max_location)

Fill changes array: O(n)
Scan array: O(1001) = O(1) (constant)
Total: O(n)

Better than O(n log n) when locations limited! 🎯

Space Complexity: O(max_location) = O(1001) = O(1)

Fixed-size array

---

🎯 Key Insights Summary

The Four Critical Points:

1. Event-Based Thinking (Like Meeting Rooms II)

Car Pooling = Meeting Rooms II with weights!

Meeting Rooms II:
  - Count concurrent meetings
  - Events: start/end

Car Pooling:
  - Sum concurrent passengers
  - Events: pickup/dropoff with counts

Same pattern, different aggregation! 🔑

2. Dropoff Before Pickup at Same Location

CRITICAL ordering rule!

At same location:
  Process DROPOFF before PICKUP

Why?
  Passengers getting off free up seats
  Then new passengers can get on

  Without this: artificially inflated count!

Example:
  Location 5: drop 2, pick 3
  Correct: ...→2→0→3 (max=3)
  Wrong: ...→2→5→3 (max=5, but false peak!)

3. Two Valid Approaches

Approach 1: Event sorting
  - Sort events by location
  - Process chronologically
  - Time: O(n log n)
  - Use when locations unbounded

Approach 2: Bucket array
  - Array indexed by location
  - Scan array
  - Time: O(n)
  - Use when locations bounded (like here!)

Choose based on constraints! ✓

4. Connection to Other Problems

This pattern appears in:
  - Meeting Rooms II (301)
  - Skyline Problem (305)
  - My Calendar problems (308-309)
  - Any "maximum concurrent" problem

Recognize the pattern = solve quickly! 🎯

---

💡 Why This Approach Works - Deep Intuition

The Timeline Simulation:

We're simulating driving from west to east:
  - At each location, update passenger count
  - Track if we ever exceed capacity

Events capture CHANGES:
  - Pickup: +passengers
  - Dropoff: -passengers

Running total = current passengers in car

This is like prefix sum but with events!

---

⚠️ Common Mistakes

// Mistake 1: Wrong sorting for same location
Collections.sort(events, (a, b) -> a[0] - b[0]); // ❌ Missing tie-break
// ✓ CORRECT: Dropoff before pickup at same location
Collections.sort(events, (a, b) -> {
    if (a[0] != b[0]) return a[0] - b[0];
    return a[1] - b[1];  // Negative (dropoff) before positive
});

// Mistake 2: Using >= instead of >
if (currentPassengers >= capacity) // ❌
// ✓ CORRECT: Exactly at capacity is OK
if (currentPassengers > capacity)

// Mistake 3: Not handling same location dropoff/pickup
// Forgetting that passengers can drop and pick at same spot
// This is why ordering matters!

// Mistake 4: Bucket array wrong indices
changes[from] -= passengers;  // ❌ Wrong direction
changes[to] += passengers;    // ❌ Wrong direction
// ✓ CORRECT:
changes[from] += passengers;  // Pickup
changes[to] -= passengers;    // Dropoff

// Mistake 5: Not scanning entire array
for (int i = 0; i < maxLocation; i++) // ❌ Might miss locations
// ✓ CORRECT: Scan all possible locations
for (int change : changes)

---

📝 Quick Revision Notes

🎯 Core Concept

Problem: Can car handle all trips without exceeding capacity?

Key Insight: Track maximum concurrent passengers!

Algorithm (Event-based): 1. Create pickup and dropoff events 2. Sort by location (dropoff before pickup if same) 3. Process events, track running total 4. If ever exceeds capacity → false

Algorithm (Bucket array): 1. Array for passenger changes at each location 2. Scan array computing running total 3. If ever exceeds capacity → false

Why It Works: Simulates timeline, tracks peak!

⚡ Quick Implementation (Event-based)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
  public boolean carPooling(int[][] trips, int capacity) {
    return sweepGreedy(trips, capacity);
  }

  private boolean sweepGreedy(int[][] trips, int k) {
    // step 1: create events with add or subtract passengers from car
    List<int[]> events = new ArrayList<>();
    for (int[] event : trips) {
      int passengers = event[0];
      int from = event[1];
      int to = event[2];

      // passengers will be get on to car in from location
      events.add(new int[] { from, passengers });
      // passengers will be get off from car in to location
      events.add(new int[] { to, -passengers });
    }

    // step 2: sort based on from and to locations.
    // if both are same, drop event should come before in sorted order
    // why? At drop off location, passengers should get down
    // before new passengers get onboarded. Else, no space in car
    Collections.sort(events, (e1, e2) -> {
      if (e1[0] != e2[0]) {
        return e1[0] - e2[0]; // sorted by location
      } else {
        return e1[1] - e2[1]; // sorted by number of passengers
      }
    });

    // step 3: now loop through all events and
    // check capacity at every event
    int capacity = 0;
    for (int[] event : events) {
      capacity += event[1];

      if (capacity > k) {
        return false;
      }
    }

    return true;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.carPooling(new int[][] { { 2, 1, 5 }, { 3, 3, 7 } }, 4) == false);
    System.out.println(s.carPooling(new int[][] { { 2, 1, 5 }, { 3, 3, 7 } }, 5) == true);
  }
}

⚡ Quick Implementation (Bucket)

public boolean carPooling(int[][] trips, int capacity) {
    int[] changes = new int[1001];

    for (int[] trip : trips) {
        changes[trip[1]] += trip[0];   // pickup
        changes[trip[2]] -= trip[0];   // dropoff
    }

    int current = 0;
    for (int change : changes) {
        current += change;
        if (current > capacity) return false;
    }
    return true;
}

🔑 Key Points

✓ Event-based: pickup (+), dropoff (-)
✓ Sort by location, dropoff before pickup
✓ Track running total of passengers
✓ Check if ever exceeds capacity
✓ Two approaches: sort O(n log n) or bucket O(n)
✓ Similar to Meeting Rooms II

🎪 Memory Aid

"Pickup adds, dropoff frees!"
"Timeline scan, capacity sees!"
"Dropoff first, no false squeeze!"
"Maximum tracked, answer with ease!" ✨

---

🎉 Congratulations!

You've mastered Car Pooling!

What You Learned:

✅ Event-based simulation - Timeline processing
✅ Dropoff before pickup - Critical ordering
✅ Two valid approaches - Sort vs bucket
✅ Pattern recognition - Like Meeting Rooms II
✅ Weighted concurrency - Sum not just count

The Beautiful Insight:

Car Pooling → Timeline Event Processing

The core insight:
  "Don't simulate every location"
  "Only process EVENTS (changes)"

  Events:
    Pickup: +passengers
    Dropoff: -passengers

  Process chronologically:
    Track running total
    Find maximum

  This is Meeting Rooms II with weights!

This pattern appears in:
  - Resource allocation over time
  - Capacity planning
  - Load balancing
  - Any "maximum concurrent load" problem

Master this = Handle capacity constraints! ✨

Interview Mastery:

When asked about Car Pooling:

1. Understand: "Can car handle all trips without exceeding capacity?"

2. Recognize: "This is like Meeting Rooms II!
   Track maximum concurrent passengers."

3. Event approach: "Create pickup and dropoff events.
   Process chronologically."

4. Critical detail: "At same location, dropoff before pickup!
   Frees seats for new passengers."

5. Two approaches: "
   Event sort: O(n log n), general
   Bucket array: O(n), when locations bounded"

6. Choose approach: "Here locations ≤ 1000, bucket is better!"

7. Algorithm: "Track running total as process events.
   If ever exceeds capacity → false."

8. Complexity: "O(n log n) for sort or O(n) for bucket
   Both O(n) space."

Shows pattern recognition and optimization! 💯

You've mastered another interval/event problem! The connection to Meeting Rooms II shows the power of pattern recognition - once you know the event-based approach, you can apply it to many problems! 🚀✨🎯