LeetCode 815: Bus Routes Solution

Master LeetCode problem 815 (Bus Routes), a hard 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.

815. Bus Routes

Hard

Array Hash Table Breadth-First Search

Problem Explanation

Explanation

To solve this problem, we can treat the bus stops as nodes in a graph and the routes as edges connecting these nodes. We can perform a breadth-first search (BFS) starting from the source bus stop to find the shortest path to the target bus stop while considering the buses we can take at each stop.

Create a map to store the list of buses that pass through each bus stop.
Perform a BFS starting from the source bus stop.
Keep track of the visited bus stops and buses taken so far.
Continue the BFS until we reach the target bus stop.
Return the minimum number of buses taken to reach the target.

Time Complexity

The time complexity of this approach is O(N * M) where N is the number of bus stops and M is the average number of buses passing through each stop.

Space Complexity

The space complexity is O(N + M) where N is the number of bus stops and M is the number of buses.

Solution Code

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        
        Map<Integer, List<Integer>> stopToBus = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopToBus.putIfAbsent(stop, new ArrayList<>());
                stopToBus.get(stop).add(i);
            }
        }
        
        Set<Integer> visitedStops = new HashSet<>();
        Set<Integer> visitedBuses = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        visitedStops.add(source);
        
        int numBuses = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            numBuses++;
            
            for (int i = 0; i < size; i++) {
                int stop = queue.poll();
                for (int bus : stopToBus.get(stop)) {
                    if (visitedBuses.contains(bus)) {
                        continue;
                    }
                    visitedBuses.add(bus);
                    for (int nextStop : routes[bus]) {
                        if (visitedStops.contains(nextStop)) {
                            continue;
                        }
                        visitedStops.add(nextStop);
                        if (nextStop == target) {
                            return numBuses;
                        }
                        queue.offer(nextStop);
                    }
                }
            }
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 815 (Bus Routes)?

This page provides optimized solutions for LeetCode problem 815 (Bus Routes) 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 815 (Bus Routes)?

The time complexity for LeetCode 815 (Bus Routes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 815 on DevExCode?

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

Back to LeetCode Solutions