Design Underground System

Medium · Arrays & Hashing · Explanation and code example

Two HashMaps + Hashing

How it works

The previous approach uses string concatenation to create route keys, which can be slow for long station names. By computing a hash value for each route instead of concatenating strings, we can achieve faster lookups. Using double hashing (two different hash functions) reduces collision probability while maintaining O(1) average lookup time.

Steps

  1. Use one hashmap to store check-in information: map passenger id to (start station, check-in time).
  2. Use another hashmap to store route statistics: map route hash to [total time, trip count].
  3. Implement a hash function that combines two polynomial rolling hashes with different bases and moduli to create a unique identifier for each route.
  4. For checkIn: Store the passenger's start station and time.
  5. For checkOut: Retrieve check-in data, compute the route hash, and update the route statistics.
  6. For getAverageTime: Compute the route hash and return total time divided by count from the route map.

Complexity

  • Time complexity:
    • O(1) time for initialization.
    • O(1) time for each checkIn() function call.
    • O(m) time for each checkOut() and getAverageTime() function calls.
  • Space complexity: O(n + N ^ 2)

Where n is the number of passengers, N is the total number of stations, and m is the average length of station name.

Things to watch for

Integer Division Instead of Float Division

When calculating the average time, using integer division will truncate the result. The problem requires a floating-point average, so ensure you cast to float before dividing.

Route Key Collision with Simple Concatenation

If station names can contain the delimiter character used in route keys, you may get false matches. For example, stations "A,B" and "C" would collide with "A" and "B,C" if using comma as delimiter.

Not Cleaning Up Check-In Data

After a passenger checks out, the check-in data is no longer needed. While not strictly incorrect, keeping stale check-in entries can waste memory in long-running systems.

Python code example

class UndergroundSystem:
    MOD1, MOD2 = 768258391, 685683731
    BASE1, BASE2 = 37, 31

    def __init__(self):
        self.checkInMap = {}  # id -> (startStation, time)
        self.routeMap = {}  # hash(route) -> (totalTime, count)

    def getHash(self, s1: str, s2: str) -> int:
        h1, h2, p1, p2 = 0, 0, 1, 1
        for c in s1 + ',' + s2:
            h1 = (h1 + (ord(c) - 96) * p1) % self.MOD1
            h2 = (h2 + (ord(c) - 96) * p2) % self.MOD2
            p1 = (p1 * self.BASE1) % self.MOD1
            p2 = (p2 * self.BASE2) % self.MOD2
        return (h1 << 32) | h2

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

    def checkOut(self, id: int, endStation: str, t: int) -> None:
        startStation, time = self.checkInMap[id]
        routeHash = self.getHash(startStation, endStation)
        if routeHash not in self.routeMap:
            self.routeMap[routeHash] = [0, 0]
        self.routeMap[routeHash][0] += t - time
        self.routeMap[routeHash][1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        routeHash = self.getHash(startStation, endStation)
        totalTime, count = self.routeMap[routeHash]
        return totalTime / count

C++ code example

class UndergroundSystem {
private:
    static constexpr int MOD1 = 768258391, MOD2 = 685683731;
    static constexpr int BASE1 = 37, BASE2 = 31;
    unordered_map<int, pair<string, int>> checkInMap;
    unordered_map<unsigned long long, pair<int, int>> routeMap;

    unsigned long long getHash(const string& s1, const string& s2) {
        long long h1 = 0, h2 = 0, p1 = 1, p2 = 1;
        string combined = s1 + "," + s2;

        for (char c : combined) {
            h1 = (h1 + (c - 96) * p1) % MOD1;
            h2 = (h2 + (c - 96) * p2) % MOD2;
            p1 = (p1 * BASE1) % MOD1;
            p2 = (p2 * BASE2) % MOD2;
        }
        return (h1 << 32) | h2;
    }

public:
    UndergroundSystem() {}

    void checkIn(int id, string startStation, int t) {
        checkInMap[id] = {startStation, t};
    }

    void checkOut(int id, string endStation, int t) {
        auto [startStation, time] = checkInMap[id];
        unsigned long long routeHash = getHash(startStation, endStation);
        routeMap[routeHash].first += (t - time);
        routeMap[routeHash].second++;
    }

    double getAverageTime(string startStation, string endStation) {
        unsigned long long routeHash = getHash(startStation, endStation);
        auto [totalTime, count] = routeMap[routeHash];
        return (double) totalTime / count;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations