Car Pooling - Practice Coding Problems

Car Pooling - Problem

Array Sorting Heap (Priority Queue) Simulation Prefix Sum Medium

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] = [numPassengers_i, from_i, to_i] indicates that the i^th trip has numPassengers_i passengers and the locations to pick them up and drop them off are from_i and to_i 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.

Input & Output

Example 1 — Exceeds Capacity

$ Input: trips = [[2,1,3],[3,2,4]], capacity = 4

› Output: false

💡 Note: At kilometer 2, we have 2 passengers from trip 1 and 3 passengers from trip 2, totaling 5 passengers which exceeds capacity 4.

Example 2 — Within Capacity

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

› Output: true

💡 Note: Maximum passengers at any point is 5 (at km 2), which equals the capacity, so it's possible.

Example 3 — Sequential Trips

$ Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11

› Output: true

💡 Note: At km 3-7: 8 passengers, km 7-9: 3 passengers. Maximum is 8 which is less than capacity 11.

Constraints

1 ≤ trips.length ≤ 1000
trips[i].length == 3
1 ≤ numPassengers_i ≤ 100
0 ≤ from_i < to_i ≤ 1000
1 ≤ capacity ≤ 100000

Visualization

Tap to expand

Understanding the Visualization

Input

Trips with pickup/dropoff locations and capacity limit

Process

Track passenger count at each location

Output

Return true if capacity never exceeded

Key Takeaway

🎯 Key Insight: Track cumulative passenger changes at pickup/dropoff points rather than checking every location individually

Asked in

U Uber 45 L Lyft 38 a Amazon 32 G Google 28

The key insight is to track passenger count changes at each location rather than simulating every kilometer. The optimal approach uses difference array technique for O(n + max_location) time complexity. For sparse locations, event-based sorting works better at O(n log n).

Common Approaches

Approach	Time	Space	Notes
✓ Bucket Array (Difference Array)	O(n + max_location)	O(max_location)	Use difference array technique for range updates
Event-Based Simulation	O(n log n)	O(n)	Use events to track passenger pickup and dropoff efficiently
Brute Force Simulation	O(n × max_location)	O(1)	Check passenger count at every possible kilometer mark

Bucket Array (Difference Array) — Algorithm Steps

Create difference array for all locations
Apply passenger changes as range updates
Compute prefix sum to get actual passenger counts
Check if any count exceeds capacity

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Diff Array

Initialize array for all locations

Apply Changes

Add at start, subtract at end

Compute Prefix

Running sum gives passenger counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int trips[][3], int tripCount, int capacity) {
    if (tripCount == 0) return true;
    
    int maxLocation = 0;
    for (int i = 0; i < tripCount; i++) {
        if (trips[i][2] > maxLocation) {
            maxLocation = trips[i][2];
        }
    }
    
    int* diff = (int*)calloc(maxLocation + 1, sizeof(int));
    
    for (int i = 0; i < tripCount; i++) {
        diff[trips[i][1]] += trips[i][0];
        diff[trips[i][2]] -= trips[i][0];
    }
    
    int currentPassengers = 0;
    for (int i = 0; i <= maxLocation; i++) {
        currentPassengers += diff[i];
        if (currentPassengers > capacity) {
            free(diff);
            return false;
        }
    }
    
    free(diff);
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for trips array
    int trips[100][3];
    int tripCount = 0;
    
    char* ptr = strchr(line, '[');
    ptr++; // Skip first [
    
    while (ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            sscanf(ptr, "%d,%d,%d", &trips[tripCount][0], &trips[tripCount][1], &trips[tripCount][2]);
            tripCount++;
            ptr = strchr(ptr, ']');
            if (ptr) ptr++;
        } else {
            ptr++;
        }
    }
    
    int capacity;
    scanf("%d", &capacity);
    
    bool result = solution(trips, tripCount, capacity);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + max_location)

O(n) to process trips, O(max_location) to compute prefix sum

✓ Linear Growth

Space Complexity

O(max_location)

Difference array of size max_location + 1

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bucket Array (Difference Array) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler