# 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**

*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/1301-1400/design-underground-system.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.