You are given an array, routes, representing bus routes where routes[i] is a bus route that the i th bus repeats forever. Every route contains one or more stations. You have also been given the source station, src, and a destination station, dest. Return the minimum number of buses someone must take to travel from src to dest, or return -1 if th…

bus-routes.js

function minimumBuses(matrix, s, d) {
  // at first we create an adj list,
  // where keys are stops
  // and values are array of buses visiting that stop

  // then we have a queue to run bfs
  // since bfs always finds shortest path in an unweighted graph
  // we add a tuple [stop, buses] to the queue
  // where buses is the number of different buses we took to reach the stop
  // initially buses is 0 since it's a starting stop

  // so we dequeue the tuple
  // then we need to add all connecting stations to the queue
  // for that we first grab the buses of dequeued stop
  // then we get stops of each bus and enqueue them with the buses + 1

  // we need to make sure we don't enqueue stops of a bus twice
  // so we need to keep track of visited buses

  // build the adj list by iterating bus routes
  const adjList = {};
  matrix.forEach((stops, bus) => {
    stops.forEach((stop) => {
      // keys are stops, values are buses visiting the stop
      adjList[stop] = adjList[stop] ?? [];
      adjList[stop].push(bus);
    });
  });

  // prepare queue for bfs
  // add starting stop and bus count to reach the stop
  // (we start from there so its initially 0)
  const queue = [[s, 0]];

  // keep track of visited buses, so each bus route only visited once
  const visitedBuses = new Set();

  while (queue.length > 0) {
    // start iterating queue
    const [stop, busCount] = queue.shift();
    // if we reached the destination,
    // busCount will be the number of different buses we used to reach the stop
    if (stop === d) {
      return busCount;
    }
    // grab the list of buses visiting the stop from the adj list we've built
    const stopBuses = adjList[stop];
    stopBuses.forEach((bus) => {
      // skip if we already visited this bus' stops
      if (visitedBuses.has(bus)) {
        return;
      }
      visitedBuses.add(bus);
      // enqueue stops of this bus, and for each of the stop, increment bus count
      queue.push(...matrix[bus].map((stop) => [stop, busCount + 1]));
    });
  }

  return -1;
}

export { minimumBuses };

// tc: O(number of buses * number of stops)
// sc: sam