815. Bus Routes

At a Glance

Topic: advanced-graphs
Pattern: BFS on compressed graph (routes as nodes)
Difficulty: Hard
Companies: Google, Amazon, Uber, Lyft, DoorDash
Frequency: Medium
LeetCode: 815

Problem (one-liner)

Each routes[index] lists unique stops served by that bus line (bidirectional). Find minimum buses to take from source to target. Return -1 if impossible.

Recognition Cues

Minimum transfers / hops — BFS
Stop graph can be huge — bus-line graph: edges connect routes sharing any stop
Multi-source from routes touching source

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

BFS on stops — adjacency from routes — can blow up edges — still workable with careful building — O(sum of route sizes * avg overlap).
BFS on route ids — queue routes that touch current frontier stops — same asymptotic, cleaner constant factors.

Optimal Solution

Go

func numBusesToDestination(routes [][]int, source int, target int) int {
	if source == target {
		return 0
	}
	stopToRoutes := map[int][]int{}
	for routeIndex, stops := range routes {
		for _, stop := range stops {
			stopToRoutes[stop] = append(stopToRoutes[stop], routeIndex)
		}
	}
	visitedRoute := make([]bool, len(routes))
	distance := 0
	queue := []int{}
	for _, routeIndex := range stopToRoutes[source] {
		visitedRoute[routeIndex] = true
		queue = append(queue, routeIndex)
	}
	head := 0
	for head < len(queue) {
		levelSize := len(queue) - head
		distance++
		for step := 0; step < levelSize; step++ {
			currentRoute := queue[head]
			head++
			for _, stop := range routes[currentRoute] {
				if stop == target {
					return distance
				}
				for _, nextRoute := range stopToRoutes[stop] {
					if visitedRoute[nextRoute] {
						continue
					}
					visitedRoute[nextRoute] = true
					queue = append(queue, nextRoute)
				}
			}
		}
	}
	return -1
}

JavaScript

function numBusesToDestination(routes, source, target) {
  if (source === target) {
    return 0;
  }
  const stopToRoutes = new Map();
  routes.forEach((stops, routeIndex) => {
    for (const stop of stops) {
      if (!stopToRoutes.has(stop)) {
        stopToRoutes.set(stop, []);
      }
      stopToRoutes.get(stop).push(routeIndex);
    }
  });
  const visitedRoute = new Array(routes.length).fill(false);
  const queue = [];
  for (const routeIndex of stopToRoutes.get(source) ?? []) {
    visitedRoute[routeIndex] = true;
    queue.push(routeIndex);
  }
  let distance = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    distance += 1;
    for (let step = 0; step < levelSize; step += 1) {
      const currentRoute = queue.shift();
      for (const stop of routes[currentRoute]) {
        if (stop === target) {
          return distance;
        }
        for (const nextRoute of stopToRoutes.get(stop) ?? []) {
          if (visitedRoute[nextRoute]) {
            continue;
          }
          visitedRoute[nextRoute] = true;
          queue.push(nextRoute);
        }
      }
    }
  }
  return -1;
}

Map each stop to route ids. BFS from routes covering source; each hop traverses one bus line to any shared stop, enqueue unseen routes touching those stops. First time you dequeue onto target stop scan, distance equals number of buses.

Invariant: distance counts bus edges used; route visitation prevents repeating the same line.

Edge Cases

source == target — 0 buses
Disconnected components — BFS ends with -1
Same route covers both ends — 1 bus

Pitfalls

BFS on stops without marking routes — can revisit infinite loops with same bus
Building dense stop-stop adjacency — unnecessary; route-layer graph suffices

Variants

Weighted lines (transfer time) — Dijkstra on route graph.
Capacity constraints per route — min-cost flow.
Dynamic route closures — replan with incremental BFS.

Mind-Map Tags

#bfs #route-compression #multi-source #stop-to-route-index #layered-bfs