> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1301-1400/design-underground-system.md).

# 1396. Design Underground System

### Description

Implement the `UndergroundSystem` class:

* `void checkIn(int id, string stationName, int t)`
  * A customer with a card id equal to `id`, gets in 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`, gets out from the station `stationName` at time `t`.
* `double getAverageTime(string startStation, string endStation)`
  * Returns the average time to travel between the `startStation` and the `endStation`.
  * The average time is computed from all the previous traveling from `startStation` to `endStation` that happened **directly**.
  * Call to `getAverageTime` is always valid.

You can assume all calls to `checkIn` and `checkOut` methods are consistent. If a customer gets in at time **t1** at some station, they get out at time **t2** with **t2 > t1**. All events happen in chronological order.

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/design-underground-system/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="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);

undergroundSystem.checkOut(27, "Waterloo", 20);

undergroundSystem.checkOut(32, "Cambridge", 22);

undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)

undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.00000

undergroundSystem.checkIn(10, "Leyton", 24);

undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.00000

undergroundSystem.checkOut(10, "Waterloo", 38);

undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.00000
{% endtab %}

{% tab title="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);

undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000

undergroundSystem.checkIn(5, "Leyton", 10);

undergroundSystem.checkOut(5, "Paradise", 16);

undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000

undergroundSystem.checkIn(2, "Leyton", 21);

undergroundSystem.checkOut(2, "Paradise", 30);

undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class UndergroundSystem {
    private Map<String, Pair<Double, Double>> journeyData = new HashMap<>();
    private Map<Integer, Pair<String, Integer>> checkInData = new HashMap<>();
    
    public UndergroundSystem() {
    }
    
    public void checkIn(int id, String stationName, int t) {
        checkInData.put(id, new Pair<>(stationName, t));
    }
    
    public void checkOut(int id, String stationName, int t) {
        // Look up the check in station and check in time for this id.
        // You could combine this "unpacking" into the other lines of code
        // to have less lines of code overall, but we've chosen to be verbose
        // here to make it easy for all learners to follow.
        Pair<String, Integer> checkInDataForId = checkInData.get(id);
        String startStation = checkInDataForId.getKey();
        Integer checkInTime = checkInDataForId.getValue();
        
        // Lookup the current travel time data for this route.
        String routeKey = stationsKey(startStation, stationName);
        Pair<Double, Double> routeStats  = journeyData.getOrDefault(routeKey, new Pair<>(0.0, 0.0));
        Double totalTripTime = routeStats.getKey();
        Double totalTrips = routeStats.getValue();
        
        // Update the travel time data with this trip.
        double tripTime = t - checkInTime;
        journeyData.put(routeKey, new Pair<>(totalTripTime + tripTime, totalTrips + 1));
        
        // Remove check in data for this id.
        // Note that this is optional, we'll talk about it in the space complexity analysis.
        checkInData.remove(id);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        // Lookup how many times this journey has been made, and the total time.
        String routeKey = stationsKey(startStation, endStation);
        Double totalTime = journeyData.get(routeKey).getKey();
        Double totalTrips = journeyData.get(routeKey).getValue();
        // The average is simply the total divided by the number of trips.
        return totalTime / totalTrips;
    }
    
    private String stationsKey(String startStation, String endStation) {
        return startStation + "->" + endStation;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class UndergroundSystem {
    
    private class Trip {
        int checkinTime;
        int checkoutTime;
        String checkinStation;
        String checkoutStation;
        
        Trip(int checkinTime, String checkinStation) {
            this.checkinTime = checkinTime;
            this.checkinStation = checkinStation;
        }
        
        void checkout(int time, String station) {
            this.checkoutTime = time;
            this.checkoutStation = station;
        }
    }
    
    private class Route {
        String checkinStation;
        String checkoutStation;
        int totalNoOfTrips;
        int totalTimeSpentInTrips;
        
        Route(String checkinStation, String checkoutStation) {
            this.checkinStation = checkinStation;
            this.checkoutStation = checkoutStation;
            totalNoOfTrips = 0;
            totalTimeSpentInTrips = 0;
        }
        
        void addTripTime(int checkinTime, int checkoutTime) {
            totalTimeSpentInTrips += (checkoutTime-checkinTime);
            totalNoOfTrips++;
        }
        
        double getAverageTime() {
            return (double) totalTimeSpentInTrips/totalNoOfTrips;
        }
    }
    
    private Map<Integer, Trip> tripMap;
    private Map<String, Route> routeMap;

    public UndergroundSystem() {
        this.tripMap = new HashMap();
        this.routeMap = new HashMap();
    }
    
    public void checkIn(int id, String stationName, int t) {
        if(!tripMap.containsKey(id)) {
            Trip trip = new Trip(t, stationName);
            tripMap.put(id, trip);
        }
    }
    
    public void checkOut(int id, String stationName, int t) {
        if(tripMap.containsKey(id)) {
            Trip trip = tripMap.get(id);
            trip.checkout(t, stationName);
            String routeKey = trip.checkinStation + "-" + trip.checkoutStation;
            Route route = routeMap.getOrDefault(routeKey, new Route(trip.checkinStation, trip.checkoutStation));
            route.addTripTime(trip.checkinTime, trip.checkoutTime);
            routeMap.put(routeKey, route);
            tripMap.remove(id);
        }
    }
    
    public double getAverageTime(String startStation, String endStation) {
        return routeMap.get(startStation + "-" +  endStation).getAverageTime();
    }
}

/**
 * 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);
 */
```

{% endtab %}
{% endtabs %}

### **Follow up**

*