Bus Routes

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    A city has bus routes; routes[i] lists the stops that bus i visits, and each bus runs its loop forever in both directions. You are at stop source and want to reach stop target. Return the fewest buses you must board, or −1 if it can't be done. Riding further on a bus you're already on costs nothing; only boarding counts. If source == target, the answer is 0.

    Original problem: LeetCode 815. The hard part isn't BFS itself but choosing what a BFS step means: here it's "board one more bus", not "move one stop".

    Example

    Bus 0 goes 1 → 4 → 7, bus 1 goes 7 → 9 → 12, bus 2 goes 12 → 15 and bus 3 goes 4 → 20. Getting from 1 to 15 takes three buses.
    Bus 0 goes 1 → 4 → 7, bus 1 goes 7 → 9 → 12, bus 2 goes 12 → 15 and bus 3 goes 4 → 20. Getting from 1 to 15 takes three buses.
    routes = [[1, 4, 7], [7, 9, 12], [12, 15], [4, 20]]
    source = 1, target = 15   ->  3      # bus 0, bus 1, bus 2
    source = 1, target = 20   ->  2      # bus 0 to stop 4, then bus 3
    source = 9, target = 9    ->  0
    source = 1, target = 99   -> -1      # no bus stops at 99

    Constraints (assumed)

    • 1 ≤ number of routes ≤ 500; each route has up to 10⁵ stops; total stops over all routes ≤ 10⁵.
    • Stop ids are integers up to 10⁶; a route lists each stop once.

    What this question tests

    • Modeling: picking buses (routes) as the unit of cost instead of stops.
    • A level-by-level BFS that stops as soon as the target appears.
    • Avoiding repeated work: marking routes as used, not just stops.

    Questions to ask first

    1. What if source equals target? (Here: 0, even if no bus stops there.)
    2. Do buses run in both directions? (Here: yes, every stop on a route is reachable from every other.)
    3. How big can a route be? Long routes make "connect every pair of stops" far too slow.
    4. Do we need the actual list of buses, or only the count? (Here: only the count.)