How hard is LeetCode 815. Bus Routes?

LeetCode 815. Bus Routes is rated Hard on LeetCode.

What is the time complexity of LeetCode 815. Bus Routes?

The Python solution on this page runs in O(L).

What is the space complexity of LeetCode 815. Bus Routes?

The Python solution on this page uses O(L), where L is the total number of stops on all bus routes auxiliary space.

What topics does LeetCode 815. Bus Routes cover?

LeetCode 815. Bus Routes is tagged Breadth-First Search, Array and Hash Table on LeetCode.

Bus Routes — LeetCode 815 Python Solution

HardBreadth-First SearchArrayHash Table

Problem: #815
Pattern: Breadth-First Search
Reading time: 5 min
Source: leetcode.com

The problem

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...

Example

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Python solution

Python

class Solution:
    def numBusesToDestination(
        self, routes: List[List[int]], source: int, target: int
    ) -> int:
        if source == target:
            return 0
        g = defaultdict(list)
        for i, route in enumerate(routes):
            for stop in route:
                g[stop].append(i)
        if source not in g or target not in g:
            return -1
        q = [(source, 0)]
        vis_bus = set()
        vis_stop = {source}
        for stop, bus_count in q:
            if stop == target:
                return bus_count
            for bus in g[stop]:
                if bus not in vis_bus:
                    vis_bus.add(bus)
                    for next_stop in routes[bus]:
                        if next_stop not in vis_stop:
                            vis_stop.add(next_stop)
                            q.append((next_stop, bus_count + 1))
        return -1

Complexity

Measure	Complexity
Time	O(L)
Space	O(L), where L is the total number of stops on all bus routes auxiliary

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 815. Bus Routes is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 815. Bus Routes?: LeetCode 815. Bus Routes is rated Hard on LeetCode.
What is the time complexity of LeetCode 815. Bus Routes?: The Python solution on this page runs in O(L).
What is the space complexity of LeetCode 815. Bus Routes?: The Python solution on this page uses O(L), where L is the total number of stops on all bus routes auxiliary space.
What topics does LeetCode 815. Bus Routes cover?: LeetCode 815. Bus Routes is tagged Breadth-First Search, Array and Hash Table on LeetCode.