Bus Routes

Photo by Yann Allegre on Unsplash

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

Algorithm —

For each of the bus stop, we maintain all the buses (bus routes) that go through it. To do that, we use a HashMap, where bus stop number is the key and all the buses (bus routes) that go through it are added to an HashSet.

We use BFS, where we process elements in a level-wise manner. We add the Source bus stop in the queue. Next, when we enter the while loop, we add all the bus stops that are reachable by all the bus routes that go via the Source. Thus, if we have the input as [[1, 2, 7], [3, 6, 7]] and Start as 6, then upon processing bus stop 6, we would add bus stops 3 and 7.
With this approach, all the bus stops at a given level, are “equal distance” from the start node, in terms of number of buses that need to be changed.

To avoid loops, we also maintain a HashSet that stores the buses that we have already visited.

Note that while in this approach, we use each stop for doing BFS, one could also consider each bus (route) also for BFS.

public class Solution
{
  public int NumBusesToDestination(int[][] routes, int source, int target)
  {
    // if source == target, return 0;
    if (source == target) return 0;

    // Create Dictionary, key = bus stop, values = buses stop at this stop.
    var map = new Dictionary<int, HashSet<int>>();
    int ROW = routes.Length;
    for (int i = 0; i < ROW; i++)
    {
      for (int j = 0; j < routes[i].Length; j++)
      {
        var stop = routes[i][j];
        if (!map.ContainsKey(stop)) map.Add(stop, new HashSet<int>());
        map[stop].Add(i);
      }
    }
    var visited = new HashSet<int>();
    int count = 0;
    // Create Queue, push the source as to start the BFS
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(source);
    while(queue.Count > 0) 
    {
      count++;
      int size = queue.Count;
      while (size-- > 0)
      {
        var stop = queue.Dequeue();
        // Get all buses stop at this stop
        var buses = map[stop];
        // Loop through for each bus, get all the stops from routes array, and check any stop == target
        foreach (var bus in buses)
        {
          // check the bus is already visited ?
          if (visited.Contains(bus)) continue;
          visited.Add(bus);
          // get the stops at which current bus stops
          var stops = routes[bus];
          foreach(int busStop in stops)
          {
            if (busStop == target) return count;
            queue.Enqueue(busStop);
          }
        }
      }
    }

    return -1;
  }
}