Back to solutions

Design Underground System

MediumArrays

Track check-ins/outs and report average travel time between stations.

Open problem
Constraints
  • 1 <= q <= 10^4
  • times are non-negative integers

Two maps: in-progress and totals

Time O(1) per operationSpace O(passengers + station pairs)

Keep one map from passenger id to their (start station, check-in time) for trips in progress, and another from a (start, end) station pair to the running sum of times and the trip count. On check-out, look up the start, add the elapsed time to that pair's totals, and clear the in-progress entry. The average is sum divided by count.

Key terms
running total:
A sum and count maintained so the average is available without rescanning trips.
trip key:
The (start, end) station pair identifying a route.
void checkOut(int id, const string& e, int t) {
    auto [s, t0] = checkins[id];
    auto& cell = totals[{s, e}];
    cell.first += t - t0; cell.second += 1;
    checkins.erase(id);
}
double getAverageTime(const string& s, const string& e) {
    auto& cell = totals[{s, e}];
    return cell.first / cell.second;
}
Step by step
  1. checkIn: store id -> (station, time).
  2. checkOut: read the stored start and time, add (now - start time) to totals[(start, end)] and increment its count, then remove the id.
  3. getAverageTime: divide the stored sum by the count for that station pair.
  4. All operations are constant time using hash maps.