Problem Description

You need to design an underground railway system that tracks customer travel times between stations and calculates average travel times.

The system should implement a class called UndergroundSystem with three methods:

1. checkIn(id, stationName, t): Records when a customer with card ID id enters station stationName at time t. Each customer can only be checked into one station at a time.

2. checkOut(id, stationName, t): Records when a customer with card ID id exits station stationName at time t.

3. getAverageTime(startStation, endStation): Returns the average time for all trips that went directly from startStation to endStation. A direct trip means a customer checked in at startStation and then checked out at endStation without intermediate stops.

Key points to note:

• Travel time from station A to station B may differ from travel time from station B to station A (they are treated as different routes)
• When getAverageTime is called, at least one customer will have completed the specified journey
• All check-in and check-out operations are consistent: if a customer checks in at time t1 and checks out at time t2, then t1 < t2
• All events occur in chronological order

The solution uses two hash tables:

• ts: Maps customer ID to their check-in information (time, station)
• d: Maps route (startStation, endStation) to aggregated travel data (totalTime, tripCount)

When a customer checks in, their information is stored. When they check out, the travel time is calculated and added to the route statistics. The average time is computed by dividing the total time by the number of trips for that specific route.

Intuition

To track travel times between stations, we need to solve two main challenges: tracking individual customer journeys and calculating averages for specific routes.

First, let's think about what happens during a customer's journey. When someone checks in, we don't know their destination yet - we only know their starting point and time. When they check out, we finally have the complete journey information. This suggests we need temporary storage for incomplete journeys.

For tracking incomplete journeys, we need to associate each customer's check-in information with their ID. A hash table with customer ID as the key is perfect for this - we can quickly store and retrieve check-in data when the customer checks out.

Once a customer checks out, we can calculate their travel time as checkOutTime - checkInTime. But here's the key insight: we don't need to store every individual journey. Since we only need averages, we can maintain running totals instead.

For calculating averages, we need two pieces of information for each route:

• The total time spent by all customers on that route
• The number of trips completed on that route

The average is simply totalTime / tripCount. By storing these aggregated values instead of individual trips, we save memory and make the average calculation instantaneous.

The route itself can be represented as a tuple (startStation, endStation). This is important because the problem states that A→B and B→A are different routes with potentially different average times.

This leads us to use two hash tables:

1. One for tracking active journeys (customers who checked in but haven't checked out yet)
2. One for storing aggregated route statistics (total time and count for each station pair)

This approach gives us O(1) time complexity for all operations and efficient memory usage since we only store aggregated data rather than individual trip records.

Solution Approach

The implementation uses two hash tables to efficiently manage the underground system data:

Data Structures:

• self.ts: A dictionary that maps customer ID to their check-in information as a tuple (time, stationName)
• self.d: A dictionary that maps route tuples (startStation, endStation) to aggregated travel data as (totalTime, tripCount)

Method Implementation:

1. __init__ method:

   • Initializes two empty dictionaries
   • self.ts = {} for tracking active check-ins
   • self.d = {} for storing route statistics

2. checkIn method:

   • When a customer checks in, we store their information in ts
   • self.ts[id] = (t, stationName)
   • This creates a temporary record that will be used when the customer checks out

3. checkOut method:

   • First, retrieve the customer's check-in information: t0, station = self.ts[id]
   • Calculate the travel time: t - t0 (current time minus check-in time)
   • Create the route key: (station, stationName) representing the complete journey
   • Update the route statistics:
     • Use get() with default (0, 0) to handle first-time routes
     • Add the travel time to the existing total: x[0] + t - t0
     • Increment the trip count: x[1] + 1
     • Store the updated values back in the dictionary

4. getAverageTime method:

   • Retrieve the route statistics: x = self.d[(startStation, endStation)]
   • Calculate the average: x[0] / x[1] (total time divided by trip count)
   • Return the result as a float

Key Implementation Details:

• The solution leverages tuple keys (startStation, endStation) to uniquely identify routes, ensuring that A→B and B→A are treated as separate routes
• The get() method with default value (0, 0) elegantly handles the case when a route is encountered for the first time
• By storing aggregated data (totalTime, count) instead of individual trip times, we achieve constant time complexity for all operations
• The check-in data in self.ts can be overwritten for the same customer ID since the problem guarantees a customer can only be checked into one place at a time

This approach ensures O(1) time complexity for all three operations and uses O(P + S²) space, where P is the number of passengers currently checked in and S is the number of stations.

Example Walkthrough

Let's walk through a small example to illustrate how the UndergroundSystem works:

Scenario: Track travel times for customers traveling between stations "A", "B", and "C".

Step 1: Initialize the system

system = UndergroundSystem()
ts = {}  # Empty check-in tracker
d = {}   # Empty route statistics

Step 2: Customer 1 checks in at station "A" at time 10

checkIn(1, "A", 10)
→ ts[1] = (10, "A")

State after operation:

• ts = {1: (10, "A")}
• d = {}

Step 3: Customer 2 checks in at station "B" at time 15

checkIn(2, "B", 15)
→ ts[2] = (15, "B")

State after operation:

• ts = {1: (10, "A"), 2: (15, "B")}
• d = {}

Step 4: Customer 1 checks out at station "B" at time 25

checkOut(1, "B", 25)
→ Retrieve ts[1] = (10, "A")
→ Travel time = 25 - 10 = 15
→ Route = ("A", "B")
→ d[("A", "B")] = (15, 1)  # First trip on this route

State after operation:

• ts = {2: (15, "B")} # Customer 1's entry can be removed
• d = {("A", "B"): (15, 1)}

Step 5: Customer 2 checks out at station "C" at time 35

checkOut(2, "C", 35)
→ Retrieve ts[2] = (15, "B")
→ Travel time = 35 - 15 = 20
→ Route = ("B", "C")
→ d[("B", "C")] = (20, 1)

State after operation:

• ts = {}
• d = {("A", "B"): (15, 1), ("B", "C"): (20, 1)}

Step 6: Customer 3 checks in at "A" at time 30 and checks out at "B" at time 40

checkIn(3, "A", 30)
→ ts[3] = (30, "A")

checkOut(3, "B", 40)
→ Retrieve ts[3] = (30, "A")
→ Travel time = 40 - 30 = 10
→ Route = ("A", "B")
→ Update existing route: d[("A", "B")] = (15 + 10, 1 + 1) = (25, 2)

State after operation:

• ts = {}
• d = {("A", "B"): (25, 2), ("B", "C"): (20, 1)}

Step 7: Get average times

getAverageTime("A", "B")
→ Retrieve d[("A", "B")] = (25, 2)
→ Average = 25 / 2 = 12.5

getAverageTime("B", "C")
→ Retrieve d[("B", "C")] = (20, 1)
→ Average = 20 / 1 = 20.0

This example demonstrates:

• How check-ins are temporarily stored in ts until checkout
• How route statistics accumulate in d with running totals
• How different routes (like "A"→"B" vs "B"→"C") are tracked separately
• How averages are calculated instantly from aggregated data

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) for all operations (checkIn, checkOut, and getAverageTime)

• checkIn: Simply stores a tuple in a dictionary using the passenger ID as key, which is O(1)
• checkOut: Retrieves check-in data using passenger ID (O(1)), gets existing travel data for the station pair (O(1)), and updates the dictionary (O(1))
• getAverageTime: Retrieves the accumulated data for a station pair and performs a division operation, both O(1)

Space Complexity: O(n + m) where n is the number of passengers currently checked in and m is the number of unique station pairs

• self.ts dictionary stores check-in information for each passenger currently in the system, requiring O(n) space
• self.d dictionary stores accumulated travel time and count for each unique station pair (startStation, endStation), requiring O(m) space
• In the worst case where all passengers are checked in but not checked out, the space complexity is dominated by the number of passengers, making it effectively O(n) as stated in the reference answer

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Removing Check-in Data After Check-out

One common pitfall is leaving the check-in data in memory after a customer checks out. While this doesn't affect correctness (since the problem guarantees proper check-in/check-out sequences), it can lead to unnecessary memory usage in a real-world system with millions of customers.

Problem Code:

def checkOut(self, id: int, stationName: str, t: int) -> None:
    check_in_time, start_station = self.check_in_data[id]
    travel_time = t - check_in_time
    route = (start_station, stationName)
    total_time, trip_count = self.trip_statistics.get(route, (0, 0))
    self.trip_statistics[route] = (total_time + travel_time, trip_count + 1)
    # Missing: del self.check_in_data[id]

Solution:

def checkOut(self, id: int, stationName: str, t: int) -> None:
    check_in_time, start_station = self.check_in_data[id]
    travel_time = t - check_in_time
    route = (start_station, stationName)
    total_time, trip_count = self.trip_statistics.get(route, (0, 0))
    self.trip_statistics[route] = (total_time + travel_time, trip_count + 1)
    # Clean up the check-in data to free memory
    del self.check_in_data[id]

2. Treating Bidirectional Routes as the Same

A critical mistake is assuming that the route from station A to station B is the same as the route from station B to station A. This would give incorrect averages since travel times can differ based on direction.

Problem Code:

def checkOut(self, id: int, stationName: str, t: int) -> None:
    check_in_time, start_station = self.check_in_data[id]
    travel_time = t - check_in_time
    # Wrong: Using sorted tuple or set to make routes bidirectional
    route = tuple(sorted([start_station, stationName]))  # INCORRECT!
    # This would treat A->B and B->A as the same route

Solution: Always maintain the order of stations in the route tuple:

def checkOut(self, id: int, stationName: str, t: int) -> None:
    check_in_time, start_station = self.check_in_data[id]
    travel_time = t - check_in_time
    # Correct: Preserve the order to distinguish A->B from B->A
    route = (start_station, stationName)

3. Integer Division Instead of Float Division

In Python 2 or when using integer division, you might accidentally truncate the average time to an integer, losing precision.

Problem Code:

def getAverageTime(self, startStation: str, endStation: str) -> float:
    route = (startStation, endStation)
    total_time, trip_count = self.trip_statistics[route]
    # In Python 2 or with // operator: returns integer
    return total_time // trip_count  # INCORRECT!

Solution: Use true division to get a float result:

def getAverageTime(self, startStation: str, endStation: str) -> float:
    route = (startStation, endStation)
    total_time, trip_count = self.trip_statistics[route]
    # Correct: Use / for float division
    return total_time / trip_count

4. Not Handling Missing Routes in getAverageTime

While the problem guarantees at least one trip exists when getAverageTime is called, defensive programming would check for this condition to avoid KeyError in production code.

Enhanced Solution:

def getAverageTime(self, startStation: str, endStation: str) -> float:
    route = (startStation, endStation)
    if route not in self.trip_statistics:
        return 0.0  # or raise an exception
    total_time, trip_count = self.trip_statistics[route]
    return total_time / trip_count