Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumdifference-array

Car Pooling

Problem (restated)

Trips [numPassengers, from, to]. Capacity capacity. Can you pick up and drop off all without exceeding capacity?

Intuition

Range updates on a line: +p at from, -p at to. Scan prefix; any moment > capacity fails.

Approaches

Difference array

Tested only

Time O(n + D)Space O(D)

Idea. diff[from]+=p; diff[to]-=p; running sum is load.

Walkthrough. trips=[[2,1,5],[3,3,7]], cap=4 → load peaks at 5 → false; cap=5 → true.

Trade-offs. Sort+sweep events is equivalent; diff is O(D) when domain is small.

Solution

export function carPooling(trips: number[][], capacity: number): boolean {
  let maxTo = 0;
  for (const t of trips) maxTo = Math.max(maxTo, t[2]!);
  const diff = new Array(maxTo + 1).fill(0);
  for (const [p, f, t] of trips) {
    diff[f!]! += p!;
    diff[t!]! -= p!;
  }
  let cur = 0;
  for (const d of diff) {
    cur += d;
    if (cur > capacity) return false;
  }
  return true;
}

export function carPooling(trips: number[][], capacity: number): boolean {
  let maxTo = 0;
  for (const t of trips) maxTo = Math.max(maxTo, t[2]!);
  const diff = new Array(maxTo + 1).fill(0);
  for (const [p, f, t] of trips) {
    diff[f!]! += p!;
    diff[t!]! -= p!;
  }
  let cur = 0;
  for (const d of diff) {
    cur += d;
    if (cur > capacity) return false;
  }
  return true;
}

Template connection

Difference-array range updates then prefix reconstruct.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?