Abstract / Summary

Design a system to record subway check ins and check outs and calculate travel times between stations.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 75% (300k+ submissions).

Typical patterns to solve this problem:

• Design
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The UndergroundSystem class models a simple transit-tracking service. It records when a passenger checks in at a station, when the same passenger checks out at a destination, and can compute the average travel time between any two stations. The implementation relies on three internal containers: a dictionary for ongoing trips, and two defaultdict(int) structures that accumulate total travel time and ride counts for each station pair.

Core Data Structures

The constructor creates three attributes.

def __init__(self):
    self.total   = defaultdict(int)
    self.rides   = defaultdict(int)
    self.ongoing = {}

self.total maps a (startStation, endStation) tuple to the cumulative travel time for all completed rides of that pair. self.rides stores the number of completed rides for the same key. self.ongoing holds the active check-in information for each passenger identifier.

Check-In Process

When a passenger checks in, the method stores the station name and timestamp in self.ongoing keyed by the passenger id.

def checkIn(self, id: int, stationName: str, t: int) -> None:
    self.ongoing[id] = ( stationName, t )

The use of a plain dictionary provides constant-time insertion and lookup, which is essential when many passengers are simultaneously in the system.

Check-Out Process

The check-out routine retrieves the matching check-in record, computes the elapsed time, updates the aggregates, and removes the passenger from the active set.

def checkOut(self, id: int, stationName: str, t: int) -> None:
    startStation, startT = self.ongoing[id]
    del self.ongoing[id]

    key = ( startStation, stationName )
    self.total[key] += t - startT
    self.rides[key] += 1

Key aspects:

• The tuple (startStation, stationName) serves as a compact composite key, avoiding nested dictionaries and keeping lookups fast.
• The subtraction t - startT yields the travel duration, which is added directly to the cumulative total.
• Incrementing self.rides[key] tracks how many trips have contributed to that total.
• Deleting the entry from self.ongoing prevents unbounded growth of the active-trip map, ensuring memory usage stays proportional to the number of passengers currently in transit.

Average Time Retrieval

To obtain the average travel time between two stations, the method divides the accumulated total by the ride count for the requested pair.

def getAverageTime(self, startStation: str, endStation: str) -> float:
    key = ( startStation, endStation )
    return self.total[key] / self.rides[key]

Because self.rides[key] is incremented only after a successful check-out, division by zero cannot occur. The method works for any station pair that has at least one completed ride, including cases where the start and end stations are identical.

Edge Cases Handled

The implementation gracefully manages several boundary conditions.

• Concurrent passengers - Each passenger’s active trip is isolated by the unique id key in self.ongoing. Overlapping trips do not interfere with one another.
• Repeated check-ins - If a passenger checks in again before checking out, the new entry overwrites the previous one, ensuring that the most recent check-in is the one used for the subsequent check-out.
• Immediate check-out - A passenger can check out at the same timestamp as the check-in; the computed duration becomes zero, which is correctly added to the totals.
• Identical start and end stations - The tuple key can contain the same station name twice, allowing the system to track trips that start and end at the same location without special handling.
• Cleanup after checkout - Removing the passenger’s entry from self.ongoing eliminates stale data, preventing memory leaks even when many passengers complete trips over time.

Performance Optimizations

The code exhibits several design choices that keep operations efficient.

• Use of defaultdict(int) - This eliminates the need for explicit existence checks before updating totals and counts, reducing branching and keeping the update path tight.
• Tuple keys for aggregates - Storing the station pair as a single immutable tuple enables direct hashing and fast dictionary access, avoiding the overhead of nested structures.
• In-place arithmetic - The travel time is added to the cumulative total with a single += operation, and the ride count is incremented similarly, minimizing the number of Python bytecode instructions per update.
• Prompt removal of completed trips - By deleting entries from self.ongoing immediately after checkout, the active-trip dictionary remains small, which preserves fast lookup times and low memory footprint even under heavy load.
• No redundant data - The class stores only the minimal information required to compute averages, avoiding duplication and keeping the memory usage proportional to the number of distinct station pairs and currently active passengers.

Imagine a magical train station that keeps track of everyone riding the rails. Think of the code as a helpful robot that remembers exactly when and where people hop on and off the trains.

When someone checks in, the robot writes down their name tag number, the station they started at, and the time they arrived. It keeps this information in a special folder called ongoing so it can remember who is currently on a train.

When that same person checks out at a new station, the robot finds their info in that folder. It looks at the time they left and figures out how long the ride took by comparing it to the time they started. Once the robot does that math, it puts the information in two other folders. One folder adds up all the minutes people have spent on that specific route, and the other counts how many rides have happened on that route.

If anyone wants to know how long a trip between two places usually takes, the robot looks at those last two folders. It takes the total number of minutes spent on that route and divides it by the total number of rides. This gives the answer for the average time it takes to travel from one station to another.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go
	Progiez	C++	Python		Java
github	BigEggStudy							C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fpdjsns	C++
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality