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;
}
}