0815. Bus Routes

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.

Example 1:

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:

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

Constraints:

• 1 <= routes.length <= 500.
• 1 <= routes[i].length <= 105
• All the values of routes[i] are unique.
• sum(routes[i].length) <= 105
• 0 <= routes[i][j] < 106
• 0 <= source, target < 106

Analysis

Method 1: BFS with sort, using each route as a node

Seeing each route as a node, the edge can only be formed when two routes share one or more stops. Create a map<index, set<index>> indicates the index from routes can be used as the node. To construct this map, we will need to do a $O(n^2 \times m)$ loop to iterate and find which two routes have intersections, m is the average stop size of each route and n is the number of routes. To efficiently find the intersections, we can do a two-pointer trick, but we first need to sort each stop in each route. Then we will run a multi-source BFS to find the shortest path, which will take $O(n)$ .

Method 2: BFS using each stop as a node

Since we only care about which two stops are our source and target, and we want to know finding their related route, an easier way to construct our graph is simply by using the stop as a node. The map now looks like map<stop, vector<index>>, and it will only take $O(n \times m)$ where n is route size and m is the average size of each route's stops. Now if we run the multi-source BFS again, we might iterate through the same route multiple times, but the total times are bounded by the total number of stops, so it will be $O(n \times m)$.

Code

Method 1

// using route as node
class Solution {
public:
  int numBusesToDestination(vector<vector<int>> &routes, int source,
                            int target) {
    if (source == target)
      return 0;
    map<int, set<int>> graph; // index -> index
    int n = routes.size();
    set<int> s, e; // could be multiple source/target

    // build graph & find start and end node
    for (int i = 0; i < n; ++i) {
      set<int> a(routes[i].begin(), routes[i].end());
      if (a.count(source))
        s.insert(i);
      if (a.count(target))
        e.insert(i);
      if (a.count(target) && a.count(source))
        return 1;
      int j = 0;
      for (int r : a)
        routes[i][j++] = r;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (j == i)
          continue; // no self loop
        bool intersect = false;
        for (int a = 0, b = 0; a < routes[i].size() && b < routes[j].size();) {
          if (routes[i][a] == routes[j][b]) {
            graph[i].insert(j);
            break;
          } else if (routes[i][a] < routes[j][b]) {
            a++;
          } else {
            b++;
          }
        }
      }
    }

    if (s.empty() || e.empty())
      return -1;
    // bfs
    queue<pair<int, int>> q;
    for (int start : s) {
      q.push(make_pair(start, 1));
    }
    set<int> visited(s.begin(), s.end());
    int res = INT_MAX;
    while (!q.empty()) {
      auto p = q.front();
      q.pop();
      int t = p.first, level = p.second;

      if (e.count(t)) {
        res = min(res, level);
      }

      for (int neighbour : graph[t]) {
        if (!visited.count(neighbour)) {
          q.push(make_pair(neighbour, level + 1));
          visited.insert(neighbour);
        }
      }
    }
    return res == INT_MAX ? -1 : res;
  }
};

Method 2

// ref:
// https://leetcode.com/problems/bus-routes/discuss/122771/C++JavaPython-BFS-Solution
int numBusesToDestination(vector<vector<int>> &routes, int S, int T) {
  unordered_map<int, vector<int>> to_routes;
  for (int i = 0; i < routes.size(); ++i)
    for (int j : routes[i])
      to_routes[j].push_back(i);
  queue<pair<int, int>> bfs;
  bfs.push({S, 0});
  unordered_set<int> seen = {S};
  while (!bfs.empty()) {
    int stop = bfs.front().first, bus = bfs.front().second;
    bfs.pop();
    if (stop == T)
      return bus;
    for (int i : to_routes[stop]) {
      for (int j : routes[i]) {
        if (seen.find(j) == seen.end()) {
          seen.insert(j);
          bfs.push({j, bus + 1});
        }
      }
      routes[i].clear();
    }
  }
  return -1;
}

---

Last update: April 1, 2022