Bus Routes

For Bus Routes, the key is to treat boarding a bus as one BFS level and use a hash map from stop to route indices. That lets you jump from a stop to every bus you can board, then expand through all stops on those buses without rescanning unrelated routes. The main trade-off is controlling repeated work with visited buses and visited stops.

Problem Statement

In LeetCode 815 Bus Routes, each array in routes describes one bus that cycles through the same stops forever. You begin at the source stop without being on any bus, and you need to reach the target stop by boarding buses and transferring when two routes share a stop.

The goal is to return the minimum number of buses required, not the minimum number of stops traveled. That detail changes the search state: a correct solution counts route transfers carefully, handles the source equals target case immediately, and returns -1 when no chain of shared stops connects source to target.

Examples

Example 1

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6

Output: 2

The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Example 2

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12

Output: -1

Example details omitted.

Constraints

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 105
• All the values of routes[i] are unique.
• sum(routes[i].length) <= 105
• 0 <= routes[i][j] < 106
• 0 <= source, target < 106

Solution Approach

Build stop-to-route lookup first

Create a hash map from each stop to the list of route indices that include it. This is the core optimization for Bus Routes because scanning every route every time you stand at a stop is too slow when the total number of stops is large. With this lookup, you can instantly find which buses are available from the current stop.

Run BFS where each layer means one more bus taken

Initialize BFS from the source stop. For each stop popped from the queue, use the stop-to-route map to find all buses you can board there. For every unvisited route, mark that bus as used, then push every stop on that route into the queue. Increase the bus count by one per BFS layer so the first time you reach target, you have the minimum number of buses.

Prune repeated work aggressively

This problem fails when you revisit the same route or keep expanding the same stop from multiple buses. Use one visited set for routes and another for stops if needed. Marking routes is the most important guard because once a bus has been processed, scanning its full stop list again only repeats work and can blow up runtime on heavily overlapping routes.

Complexity Analysis

Metric	Value
Time	O(M^2 * K + M * k * \log K)
Space	O(M^2 + \log K)

Let N be the total number of stop entries across all routes. Building the stop-to-route hash map takes O(N) time. The BFS also stays O(N) overall because each route is expanded at most once, and the stops inside that route are scanned once when that bus is boarded. The space usage is O(N) for the hash map, queue, and visited sets.

What Interviewers Usually Probe

• They want you to count buses taken, so BFS levels should represent boarded routes rather than raw stop distance.
• They expect you to notice that shared stops create an implicit graph between routes and stops.
• They are testing whether you can replace repeated array scanning with a stop-to-route hash lookup.

Common Pitfalls or Variants

Common pitfalls

• Using BFS on stops without tracking bus layers can return the fewest stops traveled instead of the fewest buses taken.
• Reprocessing the same route from multiple shared stops causes massive duplicate scanning and time waste.
• Forgetting the source equals target shortcut leads to returning 1 instead of 0 on a trivial case.

Follow-up variants

• Model routes as graph nodes and connect two routes if they share at least one stop, then BFS across routes.
• Run bidirectional BFS from source-reachable routes and target-reachable routes when overlap is dense.
• Return an actual transfer path by storing parent route or parent stop information during BFS.

FAQ

What is the best pattern for LeetCode 815 Bus Routes?

The best pattern is BFS combined with a hash map from stop to route indices. The BFS level counts how many buses you have taken, while the hash lookup prevents rescanning unrelated routes for every stop.

Why is BFS the right choice for Bus Routes?

Each bus ride adds one unit to the answer, so the problem naturally fits unweighted shortest path search. BFS guarantees that the first time you reach the target stop, you used the minimum number of buses.

Should I mark stops or routes as visited?

Marking routes is essential because each route expansion scans its full stop list. You can also mark stops to reduce queue duplication, but skipping visited routes is the main protection against repeated work.

Can I build a graph directly between routes instead of stops?

Yes. You can connect two routes when they share a stop and then BFS from routes containing source to routes containing target. That works, but the stop-to-route hash map is often simpler and avoids explicit pairwise route graph construction.

Why does the example routes = [[1,2,7],[3,6,7]], source = 1, target = 6 return 2?

From stop 1, you can board only the first bus. That route reaches stop 7, where you can transfer to the second bus, and that second route reaches stop 6. Since you boarded two buses total, the correct answer is 2.