# Design Underground System
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-underground-system)
Canonical: https://scaleengineer.com/dsa/problems/design-underground-system
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, String
---
## Problem
An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

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`.
  * A customer can only be checked into one place at a time.
* `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 the previous traveling times from `startStation` to `endStation` that happened **directly**, meaning a check in at `startStation` followed by a check out from `endStation`.
  * The time it takes to travel from `startStation` to `endStation` **may be different** from the time it takes to travel from `endStation` to `startStation`.
  * There will be at least one customer that has traveled from `startStation` to `endStation` before `getAverageTime` is called.

You may assume all calls to the `checkIn` and `checkOut` methods are consistent. If a customer checks in at time `t1` then checks out at time `t2`, then `t1 < t2`. All events happen in chronological order.

**Example 1:**

**Input**
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

**Output**
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

**Explanation**
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

**Example 2:**

**Input**
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

**Output**
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

**Explanation**
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

**Constraints:**

* `1 <= id, t <= 106`
* `1 <= stationName.length, startStation.length, endStation.length <= 10`
* All strings consist of uppercase and lowercase English letters and digits.
* There will be at most `2 * 104` calls **in total** to `checkIn`, `checkOut`, and `getAverageTime`.
* Answers within `10-5` of the actual value will be accepted.

# Approaches
## Brute Force: Storing All Trips
This approach involves storing the details of every single trip that is completed. When a customer checks out, we calculate the travel time for their journey and add a record of this trip (start station, end station, and travel time) to a list. To find the average time for a specific route, we iterate through this entire list of trips, find all the matching ones, sum up their travel times, and divide by the count of matching trips.
**Time:** `checkIn`: O(1) - Hash map insertion is on average constant time.
`checkOut`: O(1) - Hash map lookup and list append are on average constant time.
`getAverageTime`: O(N), where N is the total number of completed trips. In the worst case, we have to scan the entire list of trips. · **Space:** O(P + N), where P is the number of passengers currently checked in, and N is the total number of completed trips. We need space to store ongoing check-ins and all historical trip data.
**Pros:** Simple to conceptualize and implement.; Fast `checkIn` and `checkOut` operations.
**Cons:** `getAverageTime` is slow, its performance degrades as more trips are completed.; High memory usage as it stores data for every single trip, which can be redundant if many trips occur on the same routes.
### Explanation
We use two main data structures:
1.  A hash map, `checkIns`, to keep track of customers who are currently on a journey. The key is the customer's `id`, and the value is an object or pair containing their `startStation` and `checkInTime`.
2.  A list, `completedTrips`, to store information about every trip that has been completed. Each element in the list would be an object containing `startStation`, `endStation`, and `travelTime`.

*   **`checkIn(id, stationName, t)`:** We simply record the check-in information by adding an entry to the `checkIns` map.
*   **`checkOut(id, stationName, t)`:** We look up the customer's check-in data from the `checkIns` map using their `id`. With the start station and start time, we can calculate the travel time. We then create a new trip record and add it to our `completedTrips` list. Finally, we remove the customer's data from the `checkIns` map as their journey is complete.
*   **`getAverageTime(startStation, endStation)`:** This is the most intensive operation. We must traverse the entire `completedTrips` list. For each trip, we check if its start and end stations match the requested route. If they do, we add its travel time to a running total and increment a counter. After checking all trips, we calculate the average by dividing the total time by the count.

```java
// Helper class to store check-in data
class CheckInData {
    String stationName;
    int time;

    public CheckInData(String stationName, int time) {
        this.stationName = stationName;
        this.time = time;
    }
}

// Helper class to store completed trip data
class Trip {
    String startStation;
    String endStation;
    int travelTime;

    public Trip(String startStation, String endStation, int travelTime) {
        this.startStation = startStation;
        this.endStation = endStation;
        this.travelTime = travelTime;
    }
}

class UndergroundSystem {
    private Map<Integer, CheckInData> checkIns;
    private List<Trip> completedTrips;

    public UndergroundSystem() {
        checkIns = new HashMap<>();
        completedTrips = new ArrayList<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkIns.put(id, new CheckInData(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        CheckInData checkInData = checkIns.get(id);
        int travelTime = t - checkInData.time;
        completedTrips.add(new Trip(checkInData.stationName, stationName, travelTime));
        checkIns.remove(id);
    }

    public double getAverageTime(String startStation, String endStation) {
        double totalTime = 0;
        int count = 0;
        for (Trip trip : completedTrips) {
            if (trip.startStation.equals(startStation) && trip.endStation.equals(endStation)) {
                totalTime += trip.travelTime;
                count++;
            }
        }
        return totalTime / count;
    }
}
```
### Algorithm
*   **`checkIn(id, stationName, t)`:**
    1.  Store the `stationName` and `t` associated with the customer `id` in a hash map `checkIns`.
*   **`checkOut(id, stationName, t)`:**
    1.  Retrieve the check-in data (`startStation`, `startTime`) for `id` from `checkIns`.
    2.  Calculate `travelTime = t - startTime`.
    3.  Create a new `Trip` object with `startStation`, `endStation` (`stationName`), and `travelTime`.
    4.  Add this `Trip` object to a list `completedTrips`.
    5.  Remove the entry for `id` from `checkIns`.
*   **`getAverageTime(startStation, endStation)`:**
    1.  Initialize `totalTime = 0` and `count = 0`.
    2.  Iterate through each `trip` in the `completedTrips` list.
    3.  If `trip.startStation` equals `startStation` and `trip.endStation` equals `endStation`, increment `count` and add `trip.travelTime` to `totalTime`.
    4.  Return `totalTime / count`.

## Optimized Approach using Hash Maps for Aggregated Data
This approach optimizes the `getAverageTime` operation by pre-calculating and storing the aggregated travel data for each route. Instead of storing every single trip, we maintain the total travel time and the number of trips for each unique route (`startStation` to `endStation`). When a customer checks out, we update these aggregates. This way, calculating the average time becomes a simple lookup and a division, making it extremely fast.
**Time:** `checkIn`: O(1) - Average time for hash map insertion.
`checkOut`: O(1) - Average time for hash map lookups and updates. String concatenation is fast for short strings.
`getAverageTime`: O(1) - Average time for hash map lookup. · **Space:** O(P + R), where P is the number of passengers currently checked in, and R is the number of unique routes that have been traveled. This is more memory-efficient than the brute-force approach because R is typically much smaller than the total number of trips N, especially with many repeated journeys on the same routes.
**Pros:** Extremely fast `getAverageTime` operation, with constant time complexity.; Efficient memory usage by storing aggregated data instead of individual trip records.; All operations (`checkIn`, `checkOut`, `getAverageTime`) are very fast, making the system scalable.
**Cons:** Slightly more complex to implement due to managing two separate data structures and the logic for aggregating data.; The choice of the route key (e.g., string concatenation) might have minor performance implications, though negligible in this case.
### Explanation
We use two hash maps:
1.  A hash map `checkIns` to track active journeys. It maps a customer `id` to their check-in information (`startStation` and `checkInTime`).
2.  A second hash map `routeStats` to store the aggregated data for each route. The key for this map is a string representation of the route (e.g., `"startStation:endStation"`), and the value is an object containing the `totalTravelTime` and `tripCount` for that route.

*   **`checkIn(id, stationName, t)`:** We store the check-in details in the `checkIns` map.
*   **`checkOut(id, stationName, t)`:** When a customer checks out, we retrieve their check-in data. We calculate the travel time. Then, we form a unique key for the route. We use this key to find the existing statistics in `routeStats`. We update the total time and trip count with the new trip's data. If no entry exists for this route, we create a new one. Finally, we remove the check-in data for the customer from `checkIns`.
*   **`getAverageTime(startStation, endStation)`:** We form the route key from the given stations. We look up the aggregated data in `routeStats` using this key. The average is simply `totalTravelTime / tripCount`.

```java
// Helper class for check-in data
class CheckInData {
    String stationName;
    int time;
    public CheckInData(String stationName, int time) {
        this.stationName = stationName;
        this.time = time;
    }
}

// Helper class for route statistics
class RouteStats {
    double totalTime;
    int tripCount;
    public RouteStats(double totalTime, int tripCount) {
        this.totalTime = totalTime;
        this.tripCount = tripCount;
    }
}

class UndergroundSystem {
    private Map<Integer, CheckInData> checkIns;
    private Map<String, RouteStats> routeStats;

    public UndergroundSystem() {
        checkIns = new HashMap<>();
        routeStats = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkIns.put(id, new CheckInData(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        CheckInData checkInData = checkIns.get(id);
        int travelTime = t - checkInData.time;
        String routeKey = checkInData.stationName + ":" + stationName;

        RouteStats stats = routeStats.getOrDefault(routeKey, new RouteStats(0.0, 0));
        stats.totalTime += travelTime;
        stats.tripCount++;
        routeStats.put(routeKey, stats);

        checkIns.remove(id);
    }

    public double getAverageTime(String startStation, String endStation) {
        String routeKey = startStation + ":" + endStation;
        RouteStats stats = routeStats.get(routeKey);
        return stats.totalTime / stats.tripCount;
    }
}
```
### Algorithm
*   **Data Structures:**
    *   `checkIns`: A hash map mapping customer `id` to their check-in data (`stationName`, `time`).
    *   `routeStats`: A hash map mapping a route identifier string (e.g., `"start:end"`) to an object containing `totalTime` and `tripCount`.
*   **`checkIn(id, stationName, t)`:**
    1.  Store the `stationName` and `t` for the customer `id` in the `checkIns` map.
*   **`checkOut(id, stationName, t)`:**
    1.  Retrieve the check-in data (`startStation`, `startTime`) for `id` from `checkIns`.
    2.  Calculate `travelTime = t - startTime`.
    3.  Construct a route key, e.g., `startStation + ":" + stationName`.
    4.  Fetch the current statistics for this route from `routeStats`. If none exist, create a new statistics object with zero values.
    5.  Update the statistics: add `travelTime` to `totalTime` and increment `tripCount`.
    6.  Store the updated statistics back into `routeStats`.
    7.  Remove the entry for `id` from `checkIns`.
*   **`getAverageTime(startStation, endStation)`:**
    1.  Construct the route key from `startStation` and `endStation`.
    2.  Retrieve the statistics object for this route from `routeStats`.
    3.  Return `totalTime / tripCount` from the statistics object.

# Solutions
### Java

```java
class UndergroundSystem { private Map < Integer , Integer > ts = new HashMap <>(); private Map < Integer , String > names = new HashMap <>(); private Map < String , int []> d = new HashMap <>(); public UndergroundSystem () { } public void checkIn ( int id , String stationName , int t ) { ts . put ( id , t ); names . put ( id , stationName ); } public void checkOut ( int id , String stationName , int t ) { String key = names . get ( id ) + "-" + stationName ; int [] v = d . getOrDefault ( key , new int [ 2 ]); v [ 0 ] += t - ts . get ( id ); v [ 1 ]++; d . put ( key , v ); } public double getAverageTime ( String startStation , String endStation ) { String key = startStation + "-" + endStation ; int [] v = d . get ( key ); return ( double ) v [ 0 ] / v [ 1 ]; } } /** * Your UndergroundSystem object will be instantiated and called as such: * UndergroundSystem obj = new UndergroundSystem(); * obj.checkIn(id,stationName,t); * obj.checkOut(id,stationName,t); * double param_3 = obj.getAverageTime(startStation,endStation); */
```

### CPP

```cpp
class UndergroundSystem { public: UndergroundSystem () { } void checkIn ( int id , string stationName , int t ) { ts [ id ] = { stationName , t }; } void checkOut ( int id , string stationName , int t ) { auto [ station , t0 ] = ts [ id ]; auto key = station + "-" + stationName ; auto [ tot , cnt ] = d [ key ]; d [ key ] = { tot + t - t0 , cnt + 1 }; } double getAverageTime ( string startStation , string endStation ) { auto [ tot , cnt ] = d [ startStation + "-" + endStation ]; return ( double ) tot / cnt ; } private: unordered_map < int , pair < string , int >> ts ; unordered_map < string , pair < int , int >> d ; }; /** * Your UndergroundSystem object will be instantiated and called as such: * UndergroundSystem* obj = new UndergroundSystem(); * obj->checkIn(id,stationName,t); * obj->checkOut(id,stationName,t); * double param_3 = obj->getAverageTime(startStation,endStation); */
```

### Python

```python
class UndergroundSystem : def __init__ ( self ): self . ts = {} self . d = {} def checkIn ( self , id : int , stationName : str , t : int ) -> None : self . ts [ id ] = ( t , stationName ) def checkOut ( self , id : int , stationName : str , t : int ) -> None : t0 , station = self . ts [ id ] x = self . d . get (( station , stationName ), ( 0 , 0 )) # (startStation, endStation) => (totalTime, count) # add up on all history data for start/end station self . d [( station , stationName )] = ( x [ 0 ] + t - t0 , x [ 1 ] + 1 ) def getAverageTime ( self , startStation : str , endStation : str ) -> float : x = self . d [( startStation , endStation )] return x [ 0 ] / x [ 1 ] # Your UndergroundSystem object will be instantiated and called as such: # obj = UndergroundSystem() # obj.checkIn(id,stationName,t) # obj.checkOut(id,stationName,t) # param_3 = obj.getAverageTime(startStation,endStation)
```