LeetCode 1396: Design Underground System Solution

Master LeetCode problem 1396 (Design Underground System), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1396. Design Underground System

Medium

Hash Table String Design

Problem Explanation

Explanation:

We can store the check-in information in a HashMap with the customer ID as the key and the station name and check-in time as the value.
When a customer checks out, we calculate the travel time and update a separate HashMap that stores the total travel time and the number of trips for each route.
To get the average time between two stations, we can use the data stored in the second HashMap.
The time complexity for check-in and check-out operations is O(1), and for calculating the average time is also O(1).
The space complexity is O(n) where n is the number of unique routes traveled by customers.

Solution Code

import java.util.HashMap;

class UndergroundSystem {
    private Map<Integer, Pair<String, Integer>> checkIns;
    private Map<String, Pair<Integer, Integer>> travelData;

    public UndergroundSystem() {
        checkIns = new HashMap<>();
        travelData = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkIns.put(id, new Pair<>(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> checkInData = checkIns.get(id);
        String route = checkInData.getKey() + "_" + stationName;
        
        int travelTime = t - checkInData.getValue();
        travelData.put(route, travelData.getOrDefault(route, new Pair<>(0, 0)));
        Pair<Integer, Integer> routeData = travelData.get(route);
        travelData.put(route, new Pair<>(routeData.getKey() + travelTime, routeData.getValue() + 1));
    }

    public double getAverageTime(String startStation, String endStation) {
        String route = startStation + "_" + endStation;
        Pair<Integer, Integer> routeData = travelData.get(route);
        return (double) routeData.getKey() / routeData.getValue();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1396 (Design Underground System)?

This page provides optimized solutions for LeetCode problem 1396 (Design Underground System) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1396 (Design Underground System)?

The time complexity for LeetCode 1396 (Design Underground System) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1396 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1396 in Java, C++, or Python.

Back to LeetCode Solutions