Bus Routes

hard array hash map bfs

Problem

Routes[i] is the sequence of stops served by bus i. You start at source and want to reach target; return the minimum number of buses you need to take, or −1 if impossible.

Inputroutes = [[1,2,7],[3,6,7]], source = 1, target = 6

Output2

Take bus 0 (1→7), then bus 1 (7→6). Two buses.

routes (one per ;, stops ,)

source

target

from collections import defaultdict, deque

def num_buses_to_destination(routes, source, target):
    if source == target:
        return 0
    stop_to_routes = defaultdict(list)
    for i, r in enumerate(routes):
        for s in r:
            stop_to_routes[s].append(i)
    seen_stops = {source}
    seen_routes = set()
    q = deque([(source, 0)])
    while q:
        stop, buses = q.popleft()
        for ri in stop_to_routes[stop]:
            if ri in seen_routes:
                continue
            seen_routes.add(ri)
            for ns in routes[ri]:
                if ns == target:
                    return buses + 1
                if ns not in seen_stops:
                    seen_stops.add(ns)
                    q.append((ns, buses + 1))
    return -1

function numBusesToDestination(routes, source, target) {
  if (source === target) return 0;
  const stopToRoutes = new Map();
  for (let i = 0; i < routes.length; i++) {
    for (const s of routes[i]) {
      if (!stopToRoutes.has(s)) stopToRoutes.set(s, []);
      stopToRoutes.get(s).push(i);
    }
  }
  const seenStops = new Set([source]);
  const seenRoutes = new Set();
  const q = [[source, 0]];
  while (q.length) {
    const [stop, buses] = q.shift();
    for (const ri of (stopToRoutes.get(stop) || [])) {
      if (seenRoutes.has(ri)) continue;
      seenRoutes.add(ri);
      for (const ns of routes[ri]) {
        if (ns === target) return buses + 1;
        if (!seenStops.has(ns)) { seenStops.add(ns); q.push([ns, buses + 1]); }
      }
    }
  }
  return -1;
}

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int s : routes[i]) stopToRoutes.computeIfAbsent(s, k -> new ArrayList<>()).add(i);
        }
        Set<Integer> seenStops = new HashSet<>();
        Set<Integer> seenRoutes = new HashSet<>();
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{source, 0});
        seenStops.add(source);
        while (!q.isEmpty()) {
            int[] top = q.poll();
            int stop = top[0], buses = top[1];
            for (int ri : stopToRoutes.getOrDefault(stop, Collections.emptyList())) {
                if (!seenRoutes.add(ri)) continue;
                for (int ns : routes[ri]) {
                    if (ns == target) return buses + 1;
                    if (seenStops.add(ns)) q.offer(new int[]{ns, buses + 1});
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;
        unordered_map<int, vector<int>> stopToRoutes;
        for (int i = 0; i < (int)routes.size(); i++)
            for (int s : routes[i]) stopToRoutes[s].push_back(i);
        unordered_set<int> seenStops{source}, seenRoutes;
        queue<pair<int, int>> q;
        q.push({source, 0});
        while (!q.empty()) {
            auto [stop, buses] = q.front(); q.pop();
            for (int ri : stopToRoutes[stop]) {
                if (!seenRoutes.insert(ri).second) continue;
                for (int ns : routes[ri]) {
                    if (ns == target) return buses + 1;
                    if (seenStops.insert(ns).second) q.push({ns, buses + 1});
                }
            }
        }
        return -1;
    }
};

Explanation

We want the fewest buses to get from source to target. The key insight is to do BFS over routes, not over individual stops — each "level" of the search is one more bus taken.

First we build a map stop_to_routes so that, given a stop, we instantly know which buses pass through it. Then BFS starts at the source stop with 0 buses.

From the current stop we look at every bus serving it. If we have not boarded that route before, we mark it used and add all of its stops to the frontier with buses + 1. The moment any of those stops is the target, the current bus count is the answer. We track seen_routes and seen_stops so we never re-process a bus or stop.

Example: routes=[[1,2,7],[3,6,7]], source=1, target=6. From stop 1 we board bus 0 and reach stop 7; from 7 we board bus 1 and reach 6. That is 2 buses.

Time: O(Σ|routes[i]|) Space: O(Σ|routes[i]|)