Leetcode 1396. Design Underground System

Problem

Design and implement a transit tracking system that monitors passenger movements through a transportation network. Your system needs to track when passengers enter and exit stations, then calculate the average travel time between any two stations.

The system should support three operations:

1. checkIn(passenger_id, station_name, timestamp): Record that a passenger with the given ID checked in at the specified station at the given time.
2. checkOut(passenger_id, station_name, timestamp): Record that a passenger with the given ID checked out at the specified station at the given time.
3. getAverageTime(start_station, end_station): Return the average travel time for all trips that went directly from start_station to end_station.

You can assume:

• A passenger can only be checked in at one station at a time
• Each passenger checks out before checking in again
• All queries to getAverageTime will have at least one completed trip for that route

Requirements

1. Implement the TransitTracker class with the three methods described above
2. Track active check-ins for passengers currently in transit
3. Maintain cumulative statistics (total time and trip count) for each station pair
4. Calculate averages efficiently without iterating through all past trips
5. Return the average as a floating-point number

Constraints

• 1 ≤ passenger_id, timestamp ≤ 10^6
• 1 ≤ station_name.length ≤ 10
• Station names consist of uppercase and lowercase English letters
• At most 2 × 10^4 total operations will be performed
• getAverageTime is only called when at least one trip exists for the route
• All checkIn/checkOut operations are valid (no invalid sequences)

Examples

Example 1:

` operations: ["checkIn", "checkOut", "getAverageTime"] params: [[45, "CentralStation", 3], [45, "WestTerminal", 21], ["CentralStation", "WestTerminal"]]

Output: 18.0

Explanation: Passenger 45 checks in at CentralStation at time 3 and checks out at WestTerminal at time 21. The trip duration is 21 - 3 = 18 minutes. Since this is the only trip on this route, the average is 18.0. `

Example 2:

` operations: ["checkIn", "checkIn", "checkOut", "checkOut", "getAverageTime"] params: [[10, "StationA", 5], [20, "StationA", 10], [10, "StationB", 15], [20, "StationB", 25], ["StationA", "StationB"]]

Output: 12.5

Explanation:

• Passenger 10: checks in at StationA (time 5), checks out at StationB (time 15). Duration = 10 minutes.
• Passenger 20: checks in at StationA (time 10), checks out at StationB (time 25). Duration = 15 minutes.
• Average time for StationA → StationB = (10 + 15) / 2 = 12.5 minutes. `

Example 3:

` operations: ["checkIn", "checkOut", "checkIn", "checkOut", "getAverageTime", "getAverageTime"] params: [[1, "X", 0], [1, "Y", 10], [1, "Y", 20], [1, "Z", 35], ["X", "Y"], ["Y", "Z"]]

Output: 10.0, 15.0

Explanation:

• Passenger 1 travels X → Y taking 10 minutes
• Passenger 1 later travels Y → Z taking 15 minutes
• These are tracked as separate routes with their respective averages `

Hint 1: Data Structure Design Think about what information you need to track:

• For passengers currently in transit: where did they check in and at what time?
• For completed trips: what's the total time spent and how many trips occurred for each station pair?

Consider using two separate hash maps: one for active check-ins and one for route statistics.

Hint 2: Efficient Average Calculation Instead of storing every individual trip time, maintain a running sum and count for each route. When calculating the average, simply divide the total accumulated time by the number of trips.

This approach gives you O(1) time complexity for getAverageTime queries regardless of how many trips have been recorded.

Hint 3: Route Representation How do you represent a route (station pair) as a dictionary key? You could use a tuple like (start_station, end_station) or concatenate the station names with a separator. This allows you to efficiently look up and update statistics for each unique route.

Full Solution `` Approach Explanation:

The solution uses two hash maps to efficiently track transit data:

1. Active Trips Tracking (active_trips): Maps each passenger ID to their current check-in information (station and timestamp). When a passenger checks in, we store this data. When they check out, we retrieve it to calculate the trip duration.
2. Route Statistics (route_stats): Maps each unique route (represented as a tuple of start and end stations) to cumulative statistics: total time spent and number of trips. This allows us to calculate averages in constant time without storing individual trip records.

Time Complexity:

• checkIn: O(1) - simple hash map insertion
• checkOut: O(1) - hash map lookup and update
• getAverageTime: O(1) - simple division of pre-computed values

Space Complexity:

• O(P + R) where P is the number of passengers currently in transit and R is the number of unique routes that have been traveled. In the worst case with N total operations, this is O(N).

Key Insights:

• By maintaining running totals rather than individual trip records, we avoid O(n) iteration when calculating averages
• Using tuples as dictionary keys provides a clean way to represent station pairs
• The separation of concerns (active trips vs. completed route statistics) makes the code maintainable and efficient

class TransitTracker:
    def __init__(self):
        # Track active check-ins: passenger_id -> (station_name, timestamp)
        self.active_trips = {}
        
        # Track route statistics: (start_station, end_station) -> [total_time, trip_count]
        self.route_stats = {}
    
    def checkIn(self, passenger_id: int, station_name: str, timestamp: int) -> None:
        """
        Record a passenger checking in at a station.
        Store the check-in location and time for later checkout processing.
        """
        self.active_trips[passenger_id] = (station_name, timestamp)
    
    def checkOut(self, passenger_id: int, station_name: str, timestamp: int) -> None:
        """
        Record a passenger checking out at a station.
        Calculate trip duration and update route statistics.
        """
        # Retrieve the check-in information for this passenger
        start_station, start_time = self.active_trips[passenger_id]
        
        # Calculate the trip duration
        duration = timestamp - start_time
        
        # Create route key (start_station, end_station)
        route = (start_station, station_name)
        
        # Update route statistics: add duration and increment trip count
        if route not in self.route_stats:
            self.route_stats[route] = [0, 0]  # [total_time, trip_count]
        
        self.route_stats[route][0] += duration  # Add to total time
        self.route_stats[route][1] += 1         # Increment trip count
        
        # Remove the passenger from active trips
        del self.active_trips[passenger_id]
    
    def getAverageTime(self, start_station: str, end_station: str) -> float:
        """
        Calculate and return the average travel time for a given route.
        Returns the mean of all completed trips between the two stations.
        """
        route = (start_station, end_station)
        total_time, trip_count = self.route_stats[route]
        
        # Return the average time as a float
        return total_time / trip_count