Domain 2MediumMEDIUM

Design Underground System

Track active check-ins and aggregate route statistics in a hash map for constant time lookups during queries.

Domain: medium•Updated: 2026-09-15
#hash map#dictionary#O(1) time complexity#O(N + M) space complexity

Problem Breakdown

The problem requires implementing an UndergroundSystem class to manage customer journeys between stations. We need three core functionalities:

  1. checkIn: Record a start point (station, time) for a specific ID.
  2. checkOut: Record an end point (station, time), calculate duration (end_time - start_time), and update statistics for the route pair (start_station -> end_station).
  3. getAverageTime: Retrieve the average travel time between two stations based on completed trips.

Key Constraints:

  • IDs can be large (10610^6), requiring hash maps instead of arrays to avoid sparse memory issues.
  • Routes are directional (“A” -> “B” is distinct from “B” -> “A”).
  • Consistency: A checkOut always follows a valid recent checkIn.

Intuition

To achieve O(1)O(1) 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:

  1. Active Check-ins: A dictionary mapping ID -> {stationName, checkInTime} to track where a customer currently is. This allows us to calculate duration upon checkout.
  2. 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

  1. Initialization: Initialize _active_checkins (dict) for tracking current customers and _route_stats (defaultdict) for accumulating route data.
  2. checkIn Method: Store the stationName and time t associated with the given id. This marks a customer as “in transit”.
  3. checkOut Method:
    • Retrieve the stored check-in info (start station, start time) for the given id.
    • Remove the entry from _active_checkins to 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.
  4. 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).

Complexity Analysis

  • Time Complexity:
    • checkIn: O(1)O(1) amortized. Hash map insertion depends on string length of station name (LL), bounded at 10 chars.
    • checkOut: O(1)O(1) amortized. Dictionary lookup and update are constant time relative to input size (excluding string hashing cost).
    • getAverageTime: O(1)O(1) 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 (NN).
    • 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 O(N+M)O(N + M) where N is max active users and M is unique routes.

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 defaultdict initializes [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 in route_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_in after a successful checkOut prevents 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.