Bus Routes

Problem

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.

You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

Examples

Example 1:

1
2
3
4
5


Input:
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output:
 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Example 2:

1
2
3
4


Input:
routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output:
 -1

Solution

Method 1 – Breadth-First Search (BFS) on Bus Routes

Intuition

We can model the problem as a graph where each bus route is a node, and there is an edge between two routes if they share a bus stop. By performing BFS starting from all routes containing the source stop, we can find the minimum number of buses needed to reach the target stop.

Approach

Build a mapping from each bus stop to all routes (buses) that visit it.
Start BFS from all routes that include the source stop, marking them as visited.
For each route in the queue, check if any of its stops is the target. If so, return the current bus count.
Otherwise, for each stop on the current route, enqueue all unvisited routes that also visit that stop.
Increment the bus count at each BFS level. If the target is unreachable, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
	int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
		if (source == target) return 0;
		unordered_map<int, vector<int>> stopToRoutes;
		int n = routes.size();
		for (int i = 0; i < n; ++i)
			for (int stop : routes[i])
				stopToRoutes[stop].push_back(i);
		queue<int> q;
		unordered_set<int> visited;
		for (int route : stopToRoutes[source]) {
			q.push(route);
			visited.insert(route);
		}
		int buses = 1;
		while (!q.empty()) {
			int sz = q.size();
			for (int i = 0; i < sz; ++i) {
				int route = q.front(); q.pop();
				for (int stop : routes[route]) {
					if (stop == target) return buses;
					for (int nextRoute : stopToRoutes[stop]) {
						if (!visited.count(nextRoute)) {
							visited.insert(nextRoute);
							q.push(nextRoute);
						}
					}
				}
			}
			++buses;
		}
		return -1;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func numBusesToDestination(routes [][]int, source int, target int) int {
	if source == target { return 0 }
	stopToRoutes := map[int][]int{}
	for i, route := range routes {
		for _, stop := range route {
			stopToRoutes[stop] = append(stopToRoutes[stop], i)
		}
	}
	q := []int{}
	visited := map[int]bool{}
	for _, route := range stopToRoutes[source] {
		q = append(q, route)
		visited[route] = true
	}
	buses := 1
	for len(q) > 0 {
		sz := len(q)
		for i := 0; i < sz; i++ {
			route := q[0]; q = q[1:]
			for _, stop := range routes[route] {
				if stop == target { return buses }
				for _, nextRoute := range stopToRoutes[stop] {
					if !visited[nextRoute] {
						visited[nextRoute] = true
						q = append(q, nextRoute)
					}
				}
			}
		}
		buses++
	}
	return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


import java.util.*;
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 stop : routes[i]) {
				stopToRoutes.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
			}
		}
		Queue<Integer> q = new LinkedList<>();
		Set<Integer> visited = new HashSet<>();
		for (int route : stopToRoutes.getOrDefault(source, new ArrayList<>())) {
			q.add(route);
			visited.add(route);
		}
		int buses = 1;
		while (!q.isEmpty()) {
			int sz = q.size();
			for (int i = 0; i < sz; i++) {
				int route = q.poll();
				for (int stop : routes[route]) {
					if (stop == target) return buses;
					for (int nextRoute : stopToRoutes.getOrDefault(stop, new ArrayList<>())) {
						if (!visited.contains(nextRoute)) {
							visited.add(nextRoute);
							q.add(nextRoute);
						}
					}
				}
			}
			buses++;
		}
		return -1;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
	fun numBusesToDestination(routes: Array<IntArray>, source: Int, target: Int): Int {
		if (source == target) return 0
		val stopToRoutes = mutableMapOf<Int, MutableList<Int>>()
		for (i in routes.indices) {
			for (stop in routes[i]) {
				stopToRoutes.computeIfAbsent(stop) { mutableListOf() }.add(i)
			}
		}
		val q = ArrayDeque<Int>()
		val visited = mutableSetOf<Int>()
		for (route in stopToRoutes[source] ?: emptyList()) {
			q.add(route)
			visited.add(route)
		}
		var buses = 1
		while (q.isNotEmpty()) {
			repeat(q.size) {
				val route = q.removeFirst()
				for (stop in routes[route]) {
					if (stop == target) return buses
					for (nextRoute in stopToRoutes[stop] ?: emptyList()) {
						if (nextRoute !in visited) {
							visited.add(nextRoute)
							q.add(nextRoute)
						}
					}
				}
			}
			buses++
		}
		return -1
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


from collections import deque, defaultdict
class Solution:
	def numBusesToDestination(self, routes: list[list[int]], source: int, target: int) -> int:
		if source == target:
			return 0
		stop_to_routes = defaultdict(list)
		for i, route in enumerate(routes):
			for stop in route:
				stop_to_routes[stop].append(i)
		q = deque()
		visited = set()
		for route in stop_to_routes[source]:
			q.append(route)
			visited.add(route)
		buses = 1
		while q:
			for _ in range(len(q)):
				route = q.popleft()
				for stop in routes[route]:
					if stop == target:
						return buses
					for next_route in stop_to_routes[stop]:
						if next_route not in visited:
							visited.add(next_route)
							q.append(next_route)
			buses += 1
		return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


use std::collections::{HashMap, HashSet, VecDeque};
impl Solution {
	pub fn num_buses_to_destination(routes: Vec<Vec<i32>>, source: i32, target: i32) -> i32 {
		if source == target { return 0; }
		let mut stop_to_routes: HashMap<i32, Vec<usize>> = HashMap::new();
		for (i, route) in routes.iter().enumerate() {
			for &stop in route {
				stop_to_routes.entry(stop).or_default().push(i);
			}
		}
		let mut q = VecDeque::new();
		let mut visited = HashSet::new();
		if let Some(starts) = stop_to_routes.get(&source) {
			for &route in starts {
				q.push_back(route);
				visited.insert(route);
			}
		}
		let mut buses = 1;
		while !q.is_empty() {
			for _ in 0..q.len() {
				let route = q.pop_front().unwrap();
				for &stop in &routes[route] {
					if stop == target { return buses; }
					for &next_route in stop_to_routes.get(&stop).unwrap() {
						if !visited.contains(&next_route) {
							visited.insert(next_route);
							q.push_back(next_route);
						}
					}
				}
			}
			buses += 1;
		}
		-1
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


function numBusesToDestination(routes: number[][], source: number, target: number): number {
	if (source === target) return 0;
	const stopToRoutes = new Map<number, number[]>();
	for (let i = 0; i < routes.length; i++) {
		for (const stop of routes[i]) {
			if (!stopToRoutes.has(stop)) stopToRoutes.set(stop, []);
			stopToRoutes.get(stop)!.push(i);
		}
	}
	const q: number[] = [];
	const visited = new Set<number>();
	for (const route of stopToRoutes.get(source) ?? []) {
		q.push(route);
		visited.add(route);
	}
	let buses = 1;
	while (q.length > 0) {
		const sz = q.length;
		for (let i = 0; i < sz; i++) {
			const route = q.shift()!;
			for (const stop of routes[route]) {
				if (stop === target) return buses;
				for (const nextRoute of stopToRoutes.get(stop) ?? []) {
					if (!visited.has(nextRoute)) {
						visited.add(nextRoute);
						q.push(nextRoute);
					}
				}
			}
		}
		buses++;
	}
	return -1;
}

Complexity

⏰ Time complexity: O(N * R) where N is the number of stops and R is the number of routes (buses).
🧺 Space complexity: O(N + R) for the mapping and visited sets.

Problem#

Examples#

Solution#

Method 1 – Breadth-First Search (BFS) on Bus Routes#

Intuition#

Approach#

Code#

Complexity#