Skip to content

815. Bus Routes 👍

  • Time: $O(n^2)$, where $n = |\texttt{routes}|$
  • Space: $O(n^2) + \Sigma |\texttt{routes[i]}|$
 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
class Solution {
 public:
  int numBusesToDestination(vector<vector<int>>& routes, int source,
                            int target) {
    if (source == target)
      return 0;

    unordered_map<int, vector<int>> graph;  // {route: [buses]}
    unordered_set<int> usedBuses;

    for (int i = 0; i < routes.size(); ++i)
      for (const int route : routes[i])
        graph[route].push_back(i);

    queue<int> q{{source}};

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const int route = q.front();
        q.pop();
        for (const int bus : graph[route])
          if (usedBuses.insert(bus).second)
            for (const int nextRoute : routes[bus]) {
              if (nextRoute == target)
                return step;
              q.push(nextRoute);
            }
      }

    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
class Solution {
  public int numBusesToDestination(int[][] routes, int source, int target) {
    if (source == target)
      return 0;

    Map<Integer, List<Integer>> graph = new HashMap<>(); // {route: [buses]}
    Set<Integer> usedBuses = new HashSet<>();

    for (int i = 0; i < routes.length; ++i)
      for (final int route : routes[i]) {
        graph.putIfAbsent(route, new ArrayList<>());
        graph.get(route).add(i);
      }

    Queue<Integer> q = new ArrayDeque<>(List.of(source));

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        for (final int bus : graph.getOrDefault(q.poll(), new ArrayList<>()))
          if (usedBuses.add(bus))
            for (final int nextRoute : routes[bus]) {
              if (nextRoute == target)
                return step;
              q.offer(nextRoute);
            }
      }

    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
class Solution:
  def numBusesToDestination(
      self,
      routes: list[list[int]],
      source: int,
      target: int,
  ) -> int:
    if source == target:
      return 0

    graph = collections.defaultdict(list)
    usedBuses = set()

    for i in range(len(routes)):
      for route in routes[i]:
        graph[route].append(i)

    q = collections.deque([source])

    step = 1
    while q:
      for _ in range(len(q)):
        for bus in graph[q.popleft()]:
          if bus in usedBuses:
            continue
          usedBuses.add(bus)
          for nextRoute in routes[bus]:
            if nextRoute == target:
              return step
            q.append(nextRoute)
      step += 1

    return -1