← DSA Atlas
Dedicated problem page · #815

Bus Routes

HardShortest Path, Dijkstra and Minimum Spanning TreeUnweighted shortest path (fewest transfers)BFS over buses using a stop-to-bus index
Solve on LeetCode ↗
815
HardShortest Path, Dijkstra and Minimum Spanning TreeBFS over buses using a stop-to-bus indexUnweighted shortest path (fewest transfers)

Bus Routes

You are given an array routes where routes[i] is the cyclic list of stops that the i-th bus repeats forever. You start at bus stop source and want to reach bus stop target, traveling only by buses. Return the least number of buses you must take, or -1 if it is impossible. You can board any bus at a stop it serves.

Open official problem prompt ↗
In plain English

Find the minimum number of bus boardings needed to travel from the source stop to the target stop.

Picture it like this

Like planning a subway trip counting only line changes: each new line you board costs one, and you want the fewest transfers, not the fewest stations.

Example
Input
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output
2
Why
Take bus 0 from stop 1 to stop 7, then bus 1 from stop 7 to stop 6: two buses.
Constraints
1 <= routes.length <= 5001 <= sum(routes[i].length) <= 10^5All values of routes[i] are unique within a route0 <= routes[i][j] < 10^60 <= source, target < 10^6
Pattern lesson

See the pattern, then code

Unweighted shortest path (fewest transfers)
Recognition clue

Minimizing the number of bus rides (each ride is one unit of cost) is an unweighted shortest-path count, i.e. BFS over the transfer graph.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. A 'move' is boarding one bus, not walking to one stop, so BFS should advance bus-by-bus. From any reached stop, all buses serving it become reachable in one more ride, unlocking all of their stops.

New words, made simpleKnow these before the algorithm
Transfer graph
Conceptual graph where taking a bus connects the source stop to every stop on that bus.
BFS level
The number of buses taken so far, since each ride adds one to the count.
Stop-to-bus index
A map from each stop to the buses that serve it, enabling O(1) transfer lookup.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
BFS over individual stops

Wrong cost model: it counts stops traveled, not buses boarded.

Treat each stop as a node and step stop-by-stop.

Time O(sum of routes)Space O(sum of routes)
Best choiceBFS over buses via stop index

Matches the cost model and visits each bus and stop once.

Each BFS level boards one more bus, unlocking all its stops at once.

Time O(sum of route lengths)Space O(sum of route lengths)
The rule we keep true

Invariant

When a stop is dequeued with value b, b is the minimum number of buses needed to reach that stop; each bus is expanded at most once.

Why this is correct

Reasoning

BFS explores in nondecreasing order of buses taken, so the first time target appears the count is minimal. Marking buses visited prevents reprocessing an entire route and keeps the work linear in total stops.

The algorithm in three movesSay these aloud before coding
1Map each stop to the list of buses that serve it

stop_to_buses: 1:[0],7:[0,1],6:[1]

2BFS from source; the level is the number of buses taken

level0 at stop1 -> ride bus0 -> stops 2,7 (level1)

3At each stop, expand every not-yet-ridden bus, marking all its stops reachable

at stop7 ride bus1 -> stop6==target (level2)

4Return the level when target is found, else -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
stop10
bus01
stop72
bus13
stop64
1 · Readroutes
2 · AskWhich buses serve each stop?
3 · Update state1:[0], 2:[0], 7:[0,1], 3:[1], 6:[1]
4 · ResultLookup ready
Key takeaway

Transfers: stop 1 --bus0--> stop 7 --bus1--> stop 6, two rides.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Trivial case

    If already at target, zero buses are needed.

  2. 2
    Lines 5-8Build stop-to-bus map

    For each stop, record which buses pass through it for fast transfers.

  3. 3
    Lines 9-12BFS setup

    Track visited buses and stops; queue holds (stop, buses-taken).

  4. 4
    Lines 13-17Expand buses

    For the current stop, board each unridden bus exactly once.

  5. 5
    Lines 18-24Scan a bus's stops

    Return on target, otherwise enqueue new stops at the next bus level.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • source == target -> 0 buses
  • target on no route -> -1
  • source and target share a single bus -> 1
  • Routes sharing stops enabling transfers
!

Common beginner mistakes

  • Counting stops instead of buses (BFS must advance per bus, not per stop)
  • Re-scanning a bus's full route repeatedly without a visited-buses set causes TLE
  • Forgetting the source == target shortcut returns 1 instead of 0
Check your understanding

Why do we mark whole buses as visited rather than only stops?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#1135Connecting Cities With Minimum CostMinimum spanning tree (Kruskal)