How do you solve Design Underground System?

Use two hash maps: one mapping passenger ids to their check-in info (station and time), and another mapping station pairs to a tuple of (total travel time, trip count). On check-in, record the passenger's start info. On check-out, remove the passenger's check-in info, update the route's total time and count. On average time query, return total time divided by count. This yields O(1) time for all operations and O(n) space proportional to active trips and unique routes.

What pattern does Design Underground System use?

The Pattern: Hash Maps (Stateful Aggregation) The Heuristic: Use hash maps to maintain dynamic state for ongoing entities and aggregate statistics keyed by composite identifiers, enabling constant-time updates and queries without storing all raw data.

Design Underground System — Hash Maps

Q: What is the time complexity of Design Underground System?

O(1) per operation. Each method uses hash map lookups and updates which have average O(1) time complexity, ensuring efficient handling of all calls.

Problem

Implement an underground transit system that supports check-in, check-out, and average travel time queries between stations.

1 ≤ id ≤ 10⁶
1 ≤ t ≤ 10⁹
All calls to checkIn and checkOut are consistent
At most 10⁴ calls to each method

Example

Input:

checkIn(1, "Leyton", 3), checkIn(2, "Leyton", 8), checkOut(1, "Waterloo", 15), checkOut(2, "Waterloo", 22), getAverageTime("Leyton", "Waterloo")

Output: 13.0

Passenger 1 travels from Leyton to Waterloo in 12 minutes and passenger 2 travels in 14 minutes. In the route dictionary entry for ("Leyton", "Waterloo"), the total travel time becomes 26 and the trip count becomes 2. The average returned is 26 / 2 = 13.0.

Approach

Straightforward Solution

A naive approach might store all individual trip times for each route and compute averages on demand, but this would consume excessive memory and be inefficient for large numbers of trips.

Core Observation

The problem requires tracking ongoing trips and aggregating travel times for station pairs. Each passenger's check-in data must be stored until check-out, and travel times must be accumulated and counted per route to compute averages.

Path to Optimal

Preview

The key insight is to store only the total accumulated travel time and count of trips per route, enabling O(1) average time queries. For ongoing trips, a hash map keyed by passenger id stores check-in station and time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two hash maps: one mapping passenger ids to their check-in info (station and time), and another mapping station pairs to a tuple of (total travel time, trip count). On check-in, record the passenger's start info…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1) per operation

Each method uses hash map lookups and updates which have average O(1) time complexity, ensuring efficient handling of all calls.

Space

O(n)

Space scales with the number of active check-ins and unique station pairs encountered, which is at most the number of calls made.

Solution

Python

1class UndergroundSystem:
2
3    def __init__(self):
4        self.checkins = {}
5        self.routes = {}
6
7    def checkIn(self, id: int, stationName: str, t: int) -> None:
8        self.checkins[id] = (stationName, t)
9
10    def checkOut(self, id: int, stationName: str, t: int) -> None:
11        startStation, startTime = self.checkins.pop(id)
12        route = (startStation, stationName)
13
14        total, count = self.routes.get(route, (0, 0))
15        self.routes[route] = (total + (t - startTime), count + 1)
16
17    def getAverageTime(self, startStation: str, endStation: str) -> float:
18        total, count = self.routes[(startStation, endStation)]
19        return total / count

Step-by-Step Solution

1

Record Passenger Check-In Information

  self.checkins = {}
  self.routes = {}
7def checkIn(self, id: int, stationName: str, t: int) -> None:
  self.checkins[id] = (stationName, t)

Objective

To store the check-in station and time for each passenger by their unique id.

Key Insight

Tracking ongoing trips requires a fast lookup from passenger id to their check-in data. Using a hash map keyed by id allows constant-time insertion and retrieval, enabling efficient updates when the passenger checks out.

Interview Quick-Check

Core Logic

Store passenger check-in data in a hash map keyed by id to enable O(1) retrieval during check-out.

State & Boundaries

Ensure that check-in data is overwritten if a passenger checks in again before checking out, maintaining the latest state.

Common Pitfalls & Bugs

Failing to store check-in info correctly leads to incorrect trip durations or key errors during check-out.

2

Update Route Travel Time and Trip Count on Check-Out

To compute the trip duration for a passenger and update the aggregate travel time and count for the corresponding route.

3

Calculate and Return Average Travel Time for a Route

To retrieve the total travel time and trip count for a route and compute the average travel time.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 11 Critical

startStation, startTime = self.checkins.pop(id)

Retrieve and remove the passenger's stored check-in information.

Retrieving and removing the passenger’s check-in record ensures each trip is processed exactly once and prevents stale data from remaining in the active trip map.

Line 8 Critical

self.checkins[id] = (stationName, t)

Store the passenger's starting station and timestamp.

Recording the station and time at check-in preserves the information required to compute the trip duration when the passenger checks out.

Line 15 Critical

self.routes[route] = (total + (t - startTime), count + 1)

Update the route's total travel time and increment the trip count.

Updating the cumulative travel time and trip count maintains the aggregated statistics needed to compute route averages efficiently.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why is it necessary to store both total travel time and trip count per route instead of all individual trip times?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Design Underground System from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Design Underground System drill

or drill a free problem

1	`class UndergroundSystem:`
2
3	`def __init__(self):`
4	`self.checkins = {}`
5	`self.routes = {}`
6
7	`def checkIn(self, id: int, stationName: str, t: int) -> None:`
8	`self.checkins[id] = (stationName, t)`
9
10	`def checkOut(self, id: int, stationName: str, t: int) -> None:`
11	`startStation, startTime = self.checkins.pop(id)`
12	`route = (startStation, stationName)`
13
14	`total, count = self.routes.get(route, (0, 0))`
15	`self.routes[route] = (total + (t - startTime), count + 1)`
16
17	`def getAverageTime(self, startStation: str, endStation: str) -> float:`
18	`total, count = self.routes[(startStation, endStation)]`
19	`return total / count`

4	`self.checkins = {}`
5	`self.routes = {}`
7	`def checkIn(self, id: int, stationName: str, t: int) -> None:`
8	`self.checkins[id] = (stationName, t)`