Problem

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

  • void checkIn(int id, string stationName, int t)
    • A customer with a card ID equal to id, checks in at the station stationName at time t.
    • A customer can only be checked into one place at a time.
  • void checkOut(int id, string stationName, int t)
    • A customer with a card ID equal to id, checks out from the station stationName at time t.
  • double getAverageTime(string startStation, string endStation)
    • Returns the average time it takes to travel from startStation to endStation.
    • The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
    • The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
    • There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.

You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.

Examples

Example 1:

Input

1
2

["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output

1

[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

Explanation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Example 2:

Input

1
2

["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

Output

1

[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

Explanation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

Solution

Method 1 – HashMap for Check-In and Trip Data

Intuition

To efficiently track customer journeys and compute average travel times, we use a hash map to record check-in information for each customer and another hash map to aggregate total travel times and trip counts for each station pair. This allows quick updates and queries for average times.

Approach

  1. Use a hash map to store each customer’s check-in station and time.
  2. Use another hash map to store the total time and count of trips for each (start station, end station) pair.
  3. On check-in, record the customer’s station and time.
  4. On check-out, calculate the trip duration, update the total time and count for the station pair, and remove the customer’s check-in record.
  5. On averageTime query, return the total time divided by the count for the requested station pair.

Complexity

  • ⏰ Time complexity: O(1) for all operations, as all updates and queries are direct hash map accesses.
  • 🧺 Space complexity: O(n), where n is the number of customers and station pairs tracked.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class UndergroundSystem {
    unordered_map<int, pair<string, int>> checkin;
    unordered_map<string, pair<long long, int>> trips;
public:
    void checkIn(int id, string stationName, int t) {
        checkin[id] = {stationName, t};
    }
    void checkOut(int id, string stationName, int t) {
        auto [start, time] = checkin[id];
        string key = start + "," + stationName;
        trips[key].first += t - time;
        trips[key].second++;
        checkin.erase(id);
    }
    double getAverageTime(string startStation, string endStation) {
        string key = startStation + "," + endStation;
        auto [total, count] = trips[key];
        return (double)total / count;
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class UndergroundSystem {
    private final Map<Integer, CheckIn> checkin = new HashMap<>();
    private final Map<String, Trip> trips = new HashMap<>();
    private static class CheckIn {
        String station;
        int time;
        CheckIn(String station, int time) {
            this.station = station;
            this.time = time;
        }
    }
    private static class Trip {
        long total;
        int count;
        Trip() { total = 0; count = 0; }
    }
    public void checkIn(int id, String stationName, int t) {
        checkin.put(id, new CheckIn(stationName, t));
    }
    public void checkOut(int id, String stationName, int t) {
        CheckIn ci = checkin.get(id);
        String key = ci.station + "," + stationName;
        Trip trip = trips.getOrDefault(key, new Trip());
        trip.total += t - ci.time;
        trip.count++;
        trips.put(key, trip);
        checkin.remove(id);
    }
    public double getAverageTime(String startStation, String endStation) {
        String key = startStation + "," + endStation;
        Trip trip = trips.get(key);
        return (double) trip.total / trip.count;
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class UndergroundSystem:
    def __init__(self) -> None:
        self.checkin: dict[int, tuple[str, int]] = {}
        self.trips: dict[tuple[str, str], tuple[int, int]] = {}
    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.checkin[id] = (stationName, t)
    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start, time = self.checkin.pop(id)
        key = (start, stationName)
        total, count = self.trips.get(key, (0, 0))
        self.trips[key] = (total + t - time, count + 1)
    def getAverageTime(self, startStation: str, endStation: str) -> float:
        total, count = self.trips[(startStation, endStation)]
        return total / count