Naive Approach

A naive approach would be to store all travel times for each route in a list. When getAverageTime is called, we would simply calculate the average of the travel times in the list. This is straightforward but can be inefficient if there are many trips.

Implementation

class UndergroundSystem:
    def __init__(self):
        self.check_in_data = {}
        self.route_times = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in_data[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start_station, start_time = self.check_in_data[id]
        del self.check_in_data[id]
        route = (start_station, stationName)
        travel_time = t - start_time
        if route not in self.route_times:
            self.route_times[route] = []
        self.route_times[route].append(travel_time)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        route = (startStation, endStation)
        times = self.route_times[route]
        return sum(times) / len(times)

Time and Space Complexity

• Time Complexity:
  • checkIn: O(1)
  • checkOut: O(1)
  • getAverageTime: O(N), where N is the number of trips between the two stations.
• Space Complexity: O(M), where M is the total number of trips made in the underground system. This is because we are storing all the travel times.

Optimal Approach

To improve efficiency, we can maintain running sums and counts of travel times for each route. This avoids iterating through a potentially large list every time getAverageTime is called.

Implementation

class UndergroundSystem:
    def __init__(self):
        self.check_in_data = {}
        self.route_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in_data[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start_station, start_time = self.check_in_data[id]
        del self.check_in_data[id]
        end_station = stationName
        travel_time = t - start_time
        route = (start_station, end_station)
        if route not in self.route_data:
            self.route_data[route] = [0, 0]
        self.route_data[route][0] += travel_time
        self.route_data[route][1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        route = (startStation, endStation)
        total_time, count = self.route_data[route]
        return total_time / count

Time and Space Complexity

• Time Complexity:
  • checkIn: O(1)
  • checkOut: O(1)
  • getAverageTime: O(1)
• Space Complexity: O(R), where R is the number of distinct routes. We only store a sum and a count for each route.

Edge Cases

• No Trips: The problem statement guarantees that there will be at least one trip between any two stations for which getAverageTime is called. Thus, we do not need to handle this edge case explicitly.
• Invalid Input: The problem statement assumes that all input is valid. We don't need to add explicit checks for invalid station names or times.