Log inSign up
mediumLeetCodeNot Started

Design Underground System

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

An underground railway system is keeping track of customer travel times between different stations to calculate the average travel time between any two stations.

Implement the UndergroundSystem class: - void checkIn(int id, string stationName, int t): A customer with a card ID equal to id, checks in at the station stationName at time t. - void checkOut(int id, string stationName, int t): A customer with a card ID equal to id, checks out from the station stationName at time t. - double getAverageTime(string startStation, string endStation): Returns the average time it takes to travel from startStation to endStation. The average time is computed from all previous travel times between these stations that happened directly.

Call to getAverageTime is always valid and will only be called if there has been at least one customer who checked in and checked out between startStation and endStation.

Example 1 · Example 1: Multiple Passengers:

Input: checkIn(45, "Leyton", 3), checkIn(32, "Paradise", 8), checkOut(45, "Waterloo", 15), checkOut(32, "Cambridge", 22), getAverageTime("Paradise", "Cambridge"), getAverageTime("Leyton", "Waterloo")
Output: [14.0, 12.0]
Explanation: - Passenger 45: Leyton -> Waterloo took 15 - 3 = 12 units. Average = 12.0.\n- Passenger 32: Paradise -> Cambridge took 22 - 8 = 14 units. Average = 14.0.

Constraints:

  • 1 <= id, t <= 106
  • 1 <= stationName.length, startStation.length, endStation.length <= 10
  • All strings consist of uppercase and lowercase English letters and digits.
  • At most 2 * 104 calls will be made in total to checkIn, checkOut, getAverageTime.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master transient state management versus persistent aggregate data.
  • Combine two hash maps to achieve simultaneous O(1) writes and O(1) statistical reads.
  • Implement the complete system across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Real-time event pairing (check-in / check-out pairs).
  • Continuous average computation between station pairs.
  • Strict O(1) query time requirements.

Algorithmic Decision Tree:

  • Map 1: Transient customer check-in state.
  • Map 2: Aggregated historical route statistics.

Connected Patterns:

Time Based Key-Value StoreDesign Hit CounterLogger Rate Limiter

1. Complete Trip Log Scan

Intuition

Keep track of active check-ins in a map. On check-out, record a Trip(startStation, endStation, duration) into a global list. To compute the average, filter all trips matching startStation and endStation, sum their durations, and divide by matching count.

When to apply: When getAverageTime is called rarely and historical trip storage is required.

Algorithm

  1. Step 1: In checkIn(id, station, t), store map[id] = {station, t}.
  2. Step 2: In checkOut(id, station, t), retrieve start details, calculate duration = t - startT, push Trip(start, end, duration) into trips array, and erase id from map.
  3. Step 3: In getAverageTime(start, end), scan trips array, summing durations and counting matches.
  4. Step 4: Return sum / count.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6using namespace std;
7
8struct Trip {
9 string start, end;
10 int duration;
11};
12
13class UndergroundSystem {
14 unordered_map<int, pair<string, int>> checkIns;
15 vector<Trip> allTrips;
16public:
17 UndergroundSystem() {}
18
19 void checkIn(int id, string stationName, int t) {
20 checkIns[id] = {stationName, t};
21 }
22
23 void checkOut(int id, string stationName, int t) {
24 auto [startStation, startTime] = checkIns[id];
25 checkIns.erase(id);
26 allTrips.push_back({startStation, stationName, t - startTime});
27 }
28
29 double getAverageTime(string startStation, string endStation) {
30 double total = 0;
31 int count = 0;
32 for (const auto& trip : allTrips) {
33 if (trip.start == startStation && trip.end == endStation) {
34 total += trip.duration;
35 count++;
36 }
37 }
38 return count == 0 ? 0.0 : total / count;
39 }
40};
41
42int main() {
43 UndergroundSystem sys;
44 sys.checkIn(45, "Leyton", 3);
45 sys.checkIn(32, "Paradise", 8);
46 sys.checkOut(45, "Waterloo", 15);
47 sys.checkOut(32, "Cambridge", 22);
48 cout << "Avg Paradise->Cambridge: " << sys.getAverageTime("Paradise", "Cambridge") << endl; // 14
49 cout << "Avg Leyton->Waterloo: " << sys.getAverageTime("Leyton", "Waterloo") << endl; // 12
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(1) checkIn/checkOut, O(Total Trips) getAverageTime
  • Space complexity: O(Total Trips)

2. Route Grouped Durations List

Intuition

Key the completed trips by route startStation + '->' + endStation. Each key points to a list of durations. In getAverageTime, sum only the durations recorded for that specific route.

When to apply: When per-trip breakdown is needed for specific routes.

Algorithm

  1. Step 1: In checkIn, map id to {station, t}.
  2. Step 2: In checkOut, compute duration = t - startT. Push duration to routeMap[start + -> + end].
  3. Step 3: In getAverageTime, sum list at routeMap[start + -> + end] and divide by size.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <numeric>
5#include <unordered_map>
6
7using namespace std;
8
9class UndergroundSystem {
10 unordered_map<int, pair<string, int>> checkIns;
11 unordered_map<string, vector<int>> routeTimes;
12public:
13 UndergroundSystem() {}
14
15 void checkIn(int id, string stationName, int t) {
16 checkIns[id] = {stationName, t};
17 }
18
19 void checkOut(int id, string stationName, int t) {
20 auto [startStation, startTime] = checkIns[id];
21 checkIns.erase(id);
22 string route = startStation + "->" + stationName;
23 routeTimes[route].push_back(t - startTime);
24 }
25
26 double getAverageTime(string startStation, string endStation) {
27 string route = startStation + "->" + endStation;
28 const auto& times = routeTimes[route];
29 double sum = accumulate(times.begin(), times.end(), 0.0);
30 return sum / times.size();
31 }
32};
33
34int main() {
35 UndergroundSystem sys;
36 sys.checkIn(45, "Leyton", 3);
37 sys.checkIn(32, "Paradise", 8);
38 sys.checkOut(45, "Waterloo", 15);
39 sys.checkOut(32, "Cambridge", 22);
40 cout << "Avg Paradise->Cambridge: " << sys.getAverageTime("Paradise", "Cambridge") << endl;
41 cout << "Avg Leyton->Waterloo: " << sys.getAverageTime("Leyton", "Waterloo") << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(1) checkIn/checkOut, O(Trips on Route) getAverageTime
  • Space complexity: O(Total Trips)

3. Dual Hash Map with Cumulative Aggregators

Intuition

Store active check-ins as id -> (startStation, startTime). Maintain running statistics for each route as startStation + '->' + endStation -> (totalTime, count). When a customer checks out, add their trip duration to totalTime, increment count, and delete their active check-in. In getAverageTime, return totalTime / count in O(1).

When to apply: Optimal standard for streaming analytics and real-time transit systems.

Algorithm

  1. Step 1: In checkIn(id, station, t), store checkIns[id] = (station, t).
  2. Step 2: In checkOut(id, station, t), retrieve (startStation, startTime) and erase id.
  3. Step 3: Route key = startStation + -> + stationName. Add (t - startTime) to routeStats[route].totalTime, increment routeStats[route].count.
  4. Step 4: In getAverageTime(start, end), retrieve stats for start + -> + end and return totalTime / count.

Interactive Trace for Underground System

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: checkIn(45, 'Leyton', 3)
Visual state
Values and pointers at this exact step
pointers
S
Leyton @ t=3
0
↑ checkedIn
Check / comparison
id = 45 -> ('Leyton', 3)
Decision / next transition
checkIns[45] recorded.
Why this step matters

Step 1: checkIn(45, Leyton, 3). Passenger 45 added to active check-ins map.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4
5using namespace std;
6
7class UndergroundSystem {
8 unordered_map<int, pair<string, int>> checkIns;
9 unordered_map<string, pair<long long, int>> routeStats; // route -> {totalDuration, count}
10public:
11 UndergroundSystem() {}
12
13 void checkIn(int id, string stationName, int t) {
14 checkIns[id] = {stationName, t};
15 }
16
17 void checkOut(int id, string stationName, int t) {
18 auto [startStation, startTime] = checkIns[id];
19 checkIns.erase(id);
20
21 string route = startStation + "->" + stationName;
22 routeStats[route].first += (t - startTime);
23 routeStats[route].second++;
24 }
25
26 double getAverageTime(string startStation, string endStation) {
27 string route = startStation + "->" + endStation;
28 auto [totalDuration, count] = routeStats[route];
29 return (double)totalDuration / count;
30 }
31};
32
33int main() {
34 UndergroundSystem sys;
35 sys.checkIn(45, "Leyton", 3);
36 sys.checkIn(32, "Paradise", 8);
37 sys.checkOut(45, "Waterloo", 15);
38 sys.checkOut(32, "Cambridge", 22);
39 cout << "Avg Paradise->Cambridge: " << sys.getAverageTime("Paradise", "Cambridge") << endl; // 14
40 cout << "Avg Leyton->Waterloo: " << sys.getAverageTime("Leyton", "Waterloo") << endl; // 12
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(1) strictly for all operations
  • Space complexity: O(P + R) where P = active passengers, R = unique routes

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Complete Trip Log ScanO(1) checkIn/checkOut, O(Total Trips) getAverageTimeO(Total Trips)Append every completed trip (start, end, duration) to a global list. On getAverageTime, scan all recorded trips to filter and average matching routes.Full array scan on every average calculation.
2.Better — Route Grouped Duration ListsO(1) checkIn/checkOut, O(Trips on Route) getAverageTimeO(Total Trips)Map each route key to a list of travel durations. When calculating average, sum all durations for that specific route and divide by count.Summing durations list on every query.
3.Optimal — Dual Hash Map with Cumulative AggregatorsOptimalO(1) strictly for all three operationsO(P + R) where P = active passengers, R = unique routesMaintain transient check-ins map (id -> start, time) and route aggregator map (route -> totalTime, count). Query is a single division.Hash map lookup.

Common Pitfalls & Crucial Edge Cases

Storing all individual trip durations in a list

Summing up a list of thousands of durations inside getAverageTime takes O(N) time and triggers TLE. Keep running sum and count instead.

String key delimiter collisions

Joining station names without a delimiter (e.g. start + end) can cause collisions like "A" + "BC" matching "AB" + "C". Use a delimiter like "start->end".

Not removing passenger on checkOut

Causes memory leak and breaks subsequent check-ins for that passenger.

Crucial Edge Cases to Validate:

  • Multiple passengers checking in at the same station simultaneously — Stored separately by customer ID.
  • Same passenger making multiple trips sequentially — Handled cleanly as check-in map is cleared after each check-out.
  • Floating-point precision in average calculation — Cast total time to double before dividing by count.
  • Route with only 1 completed trip — Returns that trip's exact duration.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the running average pattern: maintaining {totalTime, tripCount} allows O(1) average retrieval without storing raw histories.
  2. Emphasize object-oriented domain modeling: define clear helper classes / structs (CheckIn, RouteStats).
  3. Mention thread-safety and distributed system scaling: in real production (e.g. London Underground), check-ins are ingested via Kafka streams.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Which two primary hash maps are needed to implement Design Underground System in O(1) time per query?

2.How is getAverageTime(startStation, endStation) computed in O(1) time?

3.Why should an active passenger's entry be removed from the check-ins map on checkOut?

Back to DSA Sheet