Problem Breakdown
The problem requires implementing an UndergroundSystem class to manage customer journeys between stations. We need three core functionalities:
- checkIn: Record a start point (station, time) for a specific ID.
- checkOut: Record an end point (station, time), calculate duration (
end_time - start_time), and update statistics for the route pair(start_station -> end_station). - getAverageTime: Retrieve the average travel time between two stations based on completed trips.
Key Constraints:
- IDs can be large (), requiring hash maps instead of arrays to avoid sparse memory issues.
- Routes are directional (“A” -> “B” is distinct from “B” -> “A”).
- Consistency: A
checkOutalways follows a valid recentcheckIn.
Intuition
To achieve performance for all operations, we cannot iterate through stored trips every time getAverageTime is called. Instead, we maintain running aggregates (sum of times and count) for each unique route pair directly in memory.
We need two data structures:
- Active Check-ins: A dictionary mapping
ID -> {stationName, checkInTime}to track where a customer currently is. This allows us to calculate duration upon checkout. - Route Statistics: A nested map (or tuple-keyed dict) mapping
(startStation, endStation)->[totalDuration, tripCount].
This approach ensures that checkOut updates the statistics immediately when a journey completes, and getAverageTime simply reads pre-calculated aggregates without needing to search through history.
Approach
- Initialization: Initialize
_active_checkins(dict) for tracking current customers and_route_stats(defaultdict) for accumulating route data. - checkIn Method: Store the
stationNameand timetassociated with the givenid. This marks a customer as “in transit”. - checkOut Method:
- Retrieve the stored check-in info (start station, start time) for the given
id. - Remove the entry from
_active_checkinsto clean up state and prevent memory leaks if IDs are reused or checked in again later without clearing old entries (though constraints imply consistency). - Calculate duration:
t - checkInTime. - Construct a tuple key
(startStation, endStation)using the retrieved start station and current checkout station. - Update
_route_stats: Increment count and add to total time for this specific route pair.
- Retrieve the stored check-in info (start station, start time) for the given
- getAverageTime Method:
- Retrieve the stats list
[total_time, count]from_route_stats. - Return
total_time / count. The problem guarantees at least one trip exists before query, so division by zero is not expected based on constraints (though handled safely).
- Retrieve the stats list
Complexity Analysis
- Time Complexity:
checkIn: amortized. Hash map insertion depends on string length of station name (), bounded at 10 chars.checkOut: amortized. Dictionary lookup and update are constant time relative to input size (excluding string hashing cost).getAverageTime: amortized. Direct dictionary access.
- Space Complexity:
- We store one entry per active customer in
_active_checkins. In the worst case, this is proportional to unique IDs (). - We store statistics for each unique route pair observed. This depends on total calls or number of stations squared but practically limited by input constraints. Overall where N is max active users and M is unique routes.
- We store one entry per active customer in
Solution
import collections
class UndergroundSystem:
def __init__(self):
# Maps customer ID to their current check-in info (stationName, time)
self.check_in = {}
# Maps a tuple of stations (startStation, endStation) to [total_time, count]
self.route_stats = collections.defaultdict(lambda: [0.0, 0])
def checkIn(self, id: int, stationName: str, t: int) -> None:
"""Records the start of a journey for an ID."""
# Store current active trip info.
# We assume consistent calls where this is not already checked in elsewhere.
self.check_in[id] = (stationName, t)
def checkOut(self, id: int, stationName: str, t: int) -> None:
"""Records the end of a journey and updates route statistics."""
# Retrieve start info for this customer ID from active tracking map
if id in self.check_in:
start_station, start_time = self.check_in[id] # Start time is stored as second element
# Remove entry to clean up state immediately after checkout
del self.check_in[id]
# Calculate duration traveled on this specific leg
travel_duration = t - start_time
# Update the aggregate stats for the route (startStation -> endStation)
key = (start_station, stationName)
total_time, count = self.route_stats[key]
# Increment count and add to total time directly in defaultdict or via setitem
self.route_stats[key][0] += travel_duration
self.route_stats[key][1] += 1
def getAverageTime(self, startStation: str, endStation: str) -> float:
"""Returns average time for a specific route."""
key = (startStation, endStation)
# Constraints guarantee at least one trip exists before query.
# However, safe division handles potential edge cases gracefully.
total_time, count = self.route_stats[key]
return total_time / count if count > 0 else 0.0
# Example usage matching problem description:
# undergroundSystem = UndergroundSystem()
# undergroundSystem.checkIn(45, "Leyton", 3)
# ... (omitted for brevity in class definition)
Edge Cases Handled
- First Trip for a Route: The
defaultdictinitializes[0.0, 0]. Upon first completion, it updates correctly without needing explicit initialization checks inside the method logic beyond standard dict access behavior with defaultdicts (though we check count > 0 in getAverageTime). Division by zero is prevented because constraints guarantee at least one trip exists before query. - Route Directionality: Using
(startStation, endStation)as a tuple key ensures “A->B” and “B->A” are stored separately inroute_stats. This handles the requirement that travel times differ based on direction. - Large IDs/Names: Python dictionaries handle sparse integer keys efficiently (hash map). String hashing is efficient for short station names (max 10 chars) as per constraints.
- Memory Cleanup: Removing entries from
_check_inafter a successfulcheckOutprevents memory accumulation if the system runs indefinitely with many customers cycling through stations, ensuring space complexity remains proportional to active users rather than total history.