⚡Flashcard Drill➔
NeetCode #139LC-1396MediumArrays & Hashing
← Back to All Problems

#139 · #1396 · Design Underground System(设计地铁系统)

📌 Problem Statement & Constraints

Design an underground system supporting checkIn(id, stationName, t), checkOut(id, stationName, t) and getAverageTime(startStation, endStation). Customers make at most one trip at a time and are guaranteed to have checked in before checking out. Constraints: at most 2 * 10^4 calls.

💡 Core Algorithmic Approaches

  1. Two hash maps suffice: one from customer id to their open check-in (station, time), and one from a (start, end) station pair to the accumulated total time and trip count.
  2. checkIn records the open trip and removes it from the pending map on checkOut.
  3. checkOut computes the duration, removes the pending entry, and accumulates into the pair's running totals.
  4. getAverageTime is then a single lookup and division, giving O(1) for every operation.

💻 Benchmark Python3 Implementation

class UndergroundSystem:
    def __init__(self):
        from collections import defaultdict
        self.pending = {}                  # id -> (station, time)
        self.stats = defaultdict(lambda: [0, 0])   # (start, end) -> [total, count]

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

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start, t0 = self.pending.pop(id)   # pop removes the open trip
        key = (start, stationName)
        self.stats[key][0] += t - t0       # accumulate duration
        self.stats[key][1] += 1            # accumulate trip count

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per operation: only hash lookups and arithmetic.
💾 Space Complexity
O(customers in transit + distinct station pairs).

⚠️ Interview Pitfalls & Follow-ups

  • Storing all trips in a list and averaging on demand: O(number of trips) per query, which the problem's limits may not tolerate.
  • Forgetting to remove the pending entry on checkout: the same id could check out twice, and memory would grow.
  • Keying the statistics by the concatenated station names without a separator: ("A", "BC") and ("AB", "C") would collide. A tuple key avoids this entirely.
  • Returning an integer: the answer is a float.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems