progress

~/problems / Graphs / BFS / multi-source BFS

Bus Routes

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~40 min GooglePinterest

A city runs len(routes) bus lines. Bus i drives around the loop routes[i] forever, calling at each of its stops in turn, so you can ride it from any of its stops to any other. You can get on or off a bus at any stop it calls at, and change to another bus at a stop they share.

You are standing at stop source, not on any bus. Write fewest_buses(routes, source, target) -> int that returns the fewest buses you need to take to reach stop target, or -1 if you can't get there. Staying on one bus for many stops counts as one bus. Walking isn't allowed.

fewest_buses([[1, 4, 7], [3, 7, 9], [9, 12]], 1, 12)     # 3   (bus 0 to 7, bus 1 to 9, bus 2 to 12)
fewest_buses([[2, 5, 8], [8, 6, 11], [11, 5]], 2, 11)    # 2   (bus 0 to 8, then bus 1; or bus 0 to 5, then bus 2)
fewest_buses([[1, 2], [3, 4]], 1, 4)                     # -1  (the lines never meet)
fewest_buses([[1, 2]], 6, 6)                             # 0   (you're already there)

Constraints:

  • 1 <= len(routes) <= 500 and 1 <= len(routes[i]) <= 10^5.
  • All routes together have at most 10^5 stops. The stops on one route are distinct.
  • Stop numbers, source and target are in 0 .. 10^6 - 1. source and target need not be on any route. If source == target the answer is 0.
  • ⭐ Bonus: a speed test with routes of 50,000 stops earns a star in O(total number of stops). A search that rescans a whole route each time it reaches one of the route's stops is too slow for it.
Show hint

The answer counts buses, not stops. Think of each bus as one node: you can switch between two buses if they share a stop. Breadth-first search from the buses that call at source then counts buses directly. To keep it fast, read each bus's stop list at most once.

Topic: BFS / multi-source BFS. Level-by-level search; seed the queue with every source.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc