Sponsored
Sponsored
In this approach, we use two dictionaries to store the data: one for storing check-in information and another to store route information.
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.
1class UndergroundSystem:
2 def __init__(self):
3 self.checkInData = {}
4 self.routeData = {}
5
6 def checkIn(self, id: int, stationName: str, t: int):
7 self.checkInData[id] = (stationName, t)
8
9 def checkOut(self, id: int, stationName: str, t: int):
10 startStation, startTime = self.checkInData.pop(id)
11 route = (startStation, stationName)
12 travelTime = t - startTime
13 if route not in self.routeData:
14 self.routeData[route] = [0, 0]
15 self.routeData[route][0] += travelTime
16 self.routeData[route][1] += 1
17
18 def getAverageTime(self, startStation: str, endStation: str) -> float:
19 totalTime, count = self.routeData[(startStation, endStation)]
20 return totalTime / countThe 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.
This method uses a list and constructs a unique key using the combination of start and end stations for storing travel information.
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.
1import java.util.HashMap;
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.