Interview Coding Notes

Interview Coding Notes

Menu▾

Bus Routes: BFS Over Routes, Not Stops

LeetCode 815: routes[i] is the list of stops bus i visits in a loop. Starting at stop source, return the fewest buses you must take to reach stop target, or -1 if it is impossible.
The trap is to build a graph of stops. A route with 10^5 stops creates about 10^10 stop-to-stop edges, and the solution times out before it starts.
The key reframe: the answer counts buses, not stops, so make the buses the BFS levels. Build a map from each stop to the routes that pass through it. Then BFS where one level means one more bus boarded.
Mark a route as used the first time you board it, so you never look at it again. Each route and each stop is processed once, so the time is O(total stops across all routes). Mention the source == target edge case first.
Disclosure: I work on Linkjob AI coding interview copilot

X