Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/815.html
815. Bus Routes
Level
Hard
Description
We have a list of bus routes. Each routes[i]
is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7]
, this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.
We start at bus stop S
(initially not on a bus), and we want to go to bus stop T
. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
Example:
Input:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 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.
Note:
- 1 <= routes.length <= 500`.
- 1 <= routes[i].length <= 500`.
- 0 <= routes[i][j] < 10 ^ 6`.
Solution
Use breadth first search. Use a map to store each route and the routes that have intersection with the route (which means the two routes have at least one common stop). Use a set to store the visited routes and use another set to store the routes that can reach T
. Starting from the routes that contain S
, find the routes that have intersection with the current route, until a route that can reach T
is met.
-
class Solution { public int numBusesToDestination(int[][] routes, int S, int T) { if (S == T) return 0; Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>(); int length = routes.length; for (int i = 0; i < length; i++) Arrays.sort(routes[i]); Set<Integer> visitedSet = new HashSet<Integer>(); Set<Integer> targetRoutes = new HashSet<Integer>(); Queue<int[]> queue = new LinkedList<int[]>(); for (int i = 0; i < length; i++) { for (int j = i + 1; j < length; j++) { if (intersect(routes[i], routes[j])) { Set<Integer> set1 = map.getOrDefault(i, new HashSet<Integer>()); Set<Integer> set2 = map.getOrDefault(j, new HashSet<Integer>()); set1.add(j); set2.add(i); map.put(i, set1); map.put(j, set2); } } } for (int i = 0; i < length; i++) { int indexS = binarySearch(routes[i], S); if (indexS >= 0) { visitedSet.add(i); queue.offer(new int[]{i, 0}); } int indexT = binarySearch(routes[i], T); if (indexT >= 0) targetRoutes.add(i); } while (!queue.isEmpty()) { int[] routeDepth = queue.poll(); int routeIndex = routeDepth[0]; int depth = routeDepth[1] + 1; if (targetRoutes.contains(routeIndex)) return depth; Set<Integer> nextRoutes = map.getOrDefault(routeIndex, new HashSet<Integer>()); for (int nextRoute : nextRoutes) { if (visitedSet.add(nextRoute)) queue.offer(new int[]{nextRoute, depth}); } } return -1; } public boolean intersect(int[] route1, int[] route2) { int index1 = 0, index2 = 0; int length1 = route1.length, length2 = route2.length; while (index1 < length1 && index2 < length2) { if (route1[index1] == route2[index2]) return true; else if (route1[index1] < route2[index2]) index1++; else index2++; } return false; } public int binarySearch(int[] array, int target) { int low = 0, high = array.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; int num = array[mid]; if (num == target) return mid; else if (num > target) high = mid - 1; else low = mid + 1; } return -low - 1; } }
-
class Solution: def numBusesToDestination( self, routes: List[List[int]], source: int, target: int ) -> int: if source == target: return 0 s = [set(r) for r in routes] d = defaultdict(list) for i, r in enumerate(routes): for v in r: d[v].append(i) g = defaultdict(list) for ids in d.values(): m = len(ids) for i in range(m): for j in range(i + 1, m): a, b = ids[i], ids[j] g[a].append(b) g[b].append(a) q = deque(d[source]) ans = 1 vis = set(d[source]) while q: for _ in range(len(q)): i = q.popleft() if target in s[i]: return ans for j in g[i]: if j not in vis: vis.add(j) q.append(j) ans += 1 return -1
-
class Solution { public: int numBusesToDestination(vector<vector<int>>& routes, int source, int target) { if (source == target) { return 0; } int n = routes.size(); vector<unordered_set<int>> s(n); vector<vector<int>> g(n); unordered_map<int, vector<int>> d; for (int i = 0; i < n; ++i) { for (int v : routes[i]) { s[i].insert(v); d[v].push_back(i); } } for (auto& [_, ids] : d) { int m = ids.size(); for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { int a = ids[i], b = ids[j]; g[a].push_back(b); g[b].push_back(a); } } } queue<int> q; unordered_set<int> vis; int ans = 1; for (int v : d[source]) { q.push(v); vis.insert(v); } while (!q.empty()) { for (int k = q.size(); k; --k) { int i = q.front(); q.pop(); if (s[i].count(target)) { return ans; } for (int j : g[i]) { if (!vis.count(j)) { vis.insert(j); q.push(j); } } } ++ans; } return -1; } };
-
func numBusesToDestination(routes [][]int, source int, target int) int { if source == target { return 0 } n := len(routes) s := make([]map[int]bool, n) g := make([][]int, n) d := map[int][]int{} for i, r := range routes { for _, v := range r { if s[i] == nil { s[i] = make(map[int]bool) } s[i][v] = true d[v] = append(d[v], i) } } for _, ids := range d { m := len(ids) for i := 0; i < m; i++ { for j := i + 1; j < m; j++ { a, b := ids[i], ids[j] g[a] = append(g[a], b) g[b] = append(g[b], a) } } } q := d[source] vis := map[int]bool{} for _, v := range d[source] { vis[v] = true } ans := 1 for len(q) > 0 { for k := len(q); k > 0; k-- { i := q[0] q = q[1:] if s[i][target] { return ans } for _, j := range g[i] { if !vis[j] { vis[j] = true q = append(q, j) } } } ans++ } return -1 }