30 · Advanced Graphs: Euler Paths, Bridges & SCCs
#815 Bus Routes
the problem
In plain words
Each routes[i] lists the stops of bus i, which drives that loop forever. You stand at stop source and are not on any bus. You can move between stops only by riding buses, and you may change buses at any stop they share. Return the smallest number of buses you must board to reach stop target, or -1 if it can't be done.
in routes = [[1,2,7],[3,6,7]], source = 1, target = 6
out 2
Ride bus 0 from stop 1 to stop 7, change to bus 1, ride to stop 6.
in routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
out -1
Stop 15 is on buses 1 and 3, which only reach stops 4, 5, 15 and 19. None of them leads to stop 12.
- 1 ≤ routes.length ≤ 500
- 1 ≤ routes[i].length ≤ 10⁵; a route lists each stop once
- The total number of stop entries is at most 10⁵
- 0 ≤ routes[i][j], source, target < 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBFS shortest path (unweighted)
where this runsTransit journey planners such as RAPTOR work in rounds — round k finds journeys with at most k trips — the same "one level = one more vehicle" idea.
The cost counts buses, not stops — so make the buses the vertices. BFS level k = every bus you can be on after boarding k buses. Each bus is ridden once and each stop is used to change buses once.
solutions
From brute force to optimal
Join every pair of stops that share a bus, then BFS from source; the level of target is the number of buses.
- For each route, add an edge between every pair of its stops.
- BFS from source; the distance of a stop = buses taken.
- Return the distance of target, or -1.
A route with L stops adds L · (L − 1) edges. One 10⁵-stop route alone means about 10¹⁰ of them.
All those edges are stored.
class Solution { /** BFS over stops. Two stops are joined if one bus visits both — so every route becomes a clique. */ public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) return 0; Map<Integer, Set<Integer>> oneBus = new HashMap<>(); for (int[] route : routes) for (int a : route) for (int b : route) if (a != b) oneBus.computeIfAbsent(a, k -> new HashSet<>()).add(b); Map<Integer, Integer> buses = new HashMap<>(Map.of(source, 0)); Deque<Integer> queue = new ArrayDeque<>(List.of(source)); while (!queue.isEmpty()) { int stop = queue.poll(); for (int next : oneBus.getOrDefault(stop, Set.of())) { if (buses.containsKey(next)) continue; buses.put(next, buses.get(stop) + 1); if (next == target) return buses.get(next); queue.offer(next); } } return -1; }}Index stop → buses. Seed the queue with every bus through source (1 bus). Riding a bus, each new stop lets you change to its unboarded buses (one more bus).
- If source == target, return 0.
- Build busesAt: stop → list of buses.
- Queue every bus at source; mark them boarded; mark source seen.
- Level by level: poll a bus; for each of its stops, target → return the level; a new stop → queue its unboarded buses.
- Queue empty → -1.
Building the index reads every stop entry once; each bus is polled once and each stop's bus list is scanned only the first time the stop is seen.
The index has one entry per stop entry, plus the queue, boarded[] and the seen stops.
class Solution { /** BFS over BUSES: one level = one more bus taken. */ public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) return 0; // no bus needed Map<Integer, List<Integer>> busesAt = new HashMap<>(); // stop → buses that stop there for (int bus = 0; bus < routes.length; bus++) { for (int stop : routes[bus]) busesAt.computeIfAbsent(stop, k -> new ArrayList<>()).add(bus); } boolean[] boarded = new boolean[routes.length]; Set<Integer> seenStop = new HashSet<>(List.of(source)); Deque<Integer> queue = new ArrayDeque<>(); for (int bus : busesAt.getOrDefault(source, List.of())) { boarded[bus] = true; queue.offer(bus); // every bus through the source counts as bus #1 } for (int taken = 1; !queue.isEmpty(); taken++) { for (int size = queue.size(); size > 0; size--) { int bus = queue.poll(); for (int stop : routes[bus]) { if (stop == target) return taken; if (!seenStop.add(stop)) continue; // this stop's buses are queued already for (int next : busesAt.get(stop)) { if (boarded[next]) continue; boarded[next] = true; queue.offer(next); // change buses here } } } } return -1; // the queue ran dry: target can't be reached }}Dry run
in the room
How to say it in the interview
talk track
- Say: "The answer counts buses, so buses are my vertices; two buses are joined if they share a stop."
- Explain the stop → buses index — that's how I find my neighbours without comparing every pair of routes.
- Handle source == target first (0, even if no bus stops there).
- Complexity O(Σ route lengths); the stop-graph version is quadratic per route.
traps
- Forgetting
source == target → 0— the source may not even be on a route. - Not marking stops as seen: a busy stop's bus list is rescanned from every bus through it.
- Counting stops instead of buses (levels must be buses).
- Comparing every pair of routes for a shared stop — O(R² · L), slow for long routes.
what they ask next
Follow-ups
Return the actual buses to take?
Store parent[bus] = the bus you changed from when it was queued; walk back from the bus that reached target.
Jump Game IV (LC 1345)?
Same trick: indices with equal values form a group. After using a value's group once, clear it, or BFS becomes quadratic.
Minimise travel time, not buses?
Now edges have weights (minutes between stops), so it becomes a shortest-path problem with Dijkstra over (stop, bus) states.
before you submit
Edge cases to test
- source == target → 0, even if no bus stops there.
- target is on no route (or source is on no route) → -1.
- One bus covers both source and target → 1.
- A long chain of buses, each sharing one stop with the next → the answer is the chain length.
practise next
Similar problems
- #127Word LadderHardin Graphs
- #909Snakes and LaddersMediumin Graphs
- #787Cheapest Flights Within K StopsMediumin Shortest Paths