Bus Routes LeetCode solution in JavaScript

1
/**
2
 * @param {number[][]} routes
3
 * @param {number} source
4
 * @param {number} target
5
 * @return {number}
6
 */
7
var numBusesToDestination = function (routes, source, target) {
8
  // This map will hold an adjacency map of all the routes each stop can go to
9
  let stopRoutes = new Map();
10

11
  // Initialize adjacency map - for each route
12
  for (let route = 0; route < routes.length; route++) {
13
    // Look at all of the route's stops
14
    for (let stop of routes[route]) {
15
      // If we haven't added this stop yet then create a new entry for it
16
      if (!stopRoutes.has(stop)) stopRoutes.set(stop, new Set());
17
      // Add the current route as a possible route this stop can go to
18
      stopRoutes.get(stop).add(route);
19
    }
20
  }
21

22
  // This queue will contain all of the visited stops AND the number of buses it took to get to that stop
23
  let stopsToVisit = new Queue();
24
  // We start at the source and 0 buses to get there
25
  stopsToVisit.enqueue([source, 0]);
26

27
  // This set will contain all of the stops we've already visited
28
  let visitedStops = new Set();
29
  visitedStops.add(source);
30

31
  // This set will contain all of the routes we've visited
32
  let visitedRoutes = new Array(routes.length);
33

34
  // While there are more stops to visit
35
  while (!stopsToVisit.isEmpty()) {
36
    // Get the queued stop and number of buses it took to get there
37
    let stop = stopsToVisit.front()[0],
38
      bus = stopsToVisit.front()[1];
39
    stopsToVisit.dequeue();
40

41
    // If the stop is our target then we return the number of buses it took to get here
42
    if (stop === target) return bus;
43

44
    // Loop over all the routes this stop can go to
45
    for (let route of stopRoutes.get(stop)) {
46
      // If we've already visited this route then don't do it again
47
      if (visitedRoutes[route]) continue;
48

49
      // Loop over all of the stops in this route
50
      for (let stop of routes[route]) {
51
        // If we haven't visited this stop before
52
        if (!visitedStops.has(stop)) {
53
          // Add it to the stops we've visited
54
          visitedStops.add(stop);
55
          // Add it to the queue of stops we need to visit adding 1 more bus stop to get to it
56
          stopsToVisit.enqueue([stop, bus + 1]);
57
        }
58
      }
59

60
      // Set the current route as visited
61
      visitedRoutes[route] = true;
62
    }
63
  }
64

65
  // If we never got to our target then return -1
66
  return -1;
67
};