815 · Bus Routes — visual guide

Modeling the transit graph: bus routes are nodes, not bus stops. Boarding a bus gives free access to all its stops. Precompute a stop-to-routes index and mark entire bus lines visited to prevent $O(S^2)$ clique explosion.

Execution Stage

idle

INVARIANT Route-as-Node Invariant: Vertices in BFS are bus routes ($0 \le r < N$). Boarding route $r$ takes 1 bus and reaches all stops in $routes[r]$. Mark route $r$ visited so no bus line is boarded twice.

Buses Taken 0

Active Route -

Queue Routes 0

Press Run to trace Bus Routes BFS.

0 / 0

Speed

Java · Reference Algorithm

INTERVIEW SCRIPT

How to Present Bus Routes to an Interviewer

1. The Graph Modeling Trap

"Modeling stops as nodes causes dense clique graphs: a single bus with 500 stops has $(500 \times 499)/2 \approx 1.2 \times 10^5$ edges. Modeling the bus route itself as a node keeps the graph small ($N \le 500$)."

2. Stop-to-Route Mapping

"We build a Map<Integer, List<Integer>> stopToRoutes mapping each bus stop to all bus lines serving it in $O(\sum |routes[i]|)$."

3. Queue and Visited Semantics

"The BFS queue holds bus routes and step distance. Once route $r$ is boarded, mark visitedRoutes[r] = true so we never board it again."

4. Complexity Bound

"Every bus route and stop is inspected at most once. Time is $O(\sum |routes[i]|)$ and space is $O(\sum |routes[i]|)$."