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)
id, checks in at the station stationName at time t.void checkOut(int id, string stationName, int t)
id, checks out from the station stationName at time t.double getAverageTime(string startStation, string endStation)
startStation to endStation.startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.startStation to endStation may be different from the time it takes to travel from endStation to startStation.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 <= 1061 <= stationName.length, startStation.length, endStation.length <= 102 * 104 calls in total to checkIn, checkOut, and getAverageTime.10-5 of the actual value will be accepted.In this approach, we use two dictionaries to store the data: one for storing check-in information and another to store route information.
The Python solution uses two dictionaries, checkInData and routeData, to track check-in information and route statistics, respectively. The checkIn function stores the check-in details by mapping the ID to the station name and time. The checkOut function calculates travel time, updates the route statistics in routeData, and removes the check-in record for the customer. Finally, getAverageTime computes and returns the average travel time for the specified route.
JavaScript
C++
Time Complexity: O(1) for each operation (check-in, check-out, and get average time) because dictionary operations are constant time.
Space Complexity: O(P + R) where P is the number of passengers and R is the number of route pairs.
This method uses a list and constructs a unique key using the combination of start and end stations for storing travel information.
The Java solution utilizes helper classes, CheckInData and RouteData, to encapsulate the requisite data. The main class, UndergroundSystem, manages check-ins using checkInMap, mapping customer IDs to CheckInData. The check-out data is stored in routeMap, where travel information for each route is updated using RouteData. The average time is computed directly when requested.
C
Time Complexity: O(1) for all operations due to constant time performance of the HashMap.
Space Complexity: O(P + R), where P represents the checked-in passengers, and R is the number of unique routes.
| Approach | Complexity |
|---|---|
| Two Dictionary Method | Time Complexity: |
| List Method with String Keys | Time Complexity: |
Design Underground System - Leetcode 1396 - Python • NeetCodeIO • 9,337 views views
Watch 9 more video solutions →Practice Design Underground System with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor