Solution: Bus Routes

Let’s solve the Bus Routes problem using the Graphs pattern.

We'll cover the following

Statement#

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

Constraints:

  • 1≤1 \le routes.length ≤500\le 500
  • 1≤1 \le routes[i].length ≤103\le 10^3
  • 0≤0 \le routes[i][j] <105< 10^5
  • 0≤0 \le src, dest <105< 10^5

Solution#

The solution starts by creating an adjacency list that maps each station to the buses that travel through that station. This is done by iterating through routes and, for each route, adding the route's index to the adjacency list for each station in that route.

Next, we use the BFS algorithm to find a path from src to dest using the minimum number of buses since BFS always finds the shortest path in an unweighted graph. The BFS algorithm is implemented using a queue that stores the current station and the number of buses taken to reach that station. The queue is initialized with src and a bus count of 0.

Then, we repeatedly dequeue the next station from the queue, and if it is equal to the dest, we return the number of buses. Otherwise, we iterate through the buses that travel through the current station and, for each unvisited bus, we enqueue all the stations in that bus route along with the bus count incremented by 1 and mark that bus as visited by adding it into the set of visited buses. If the queue becomes empty and no station is equal to the dest, we return -1 because there is no route available from src to dest.

Created with Fabric.js 3.6.6 src: 2 dest: 6 Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Bus Routes 2 5 7 4 6 7 Queue (2,0) Visited Buses Graph Adjacency List Station: - Buses Taken: - ------------------------------------------------------ - From the given bus routes, an adjacency list is created.- A queue is created and a source station and bus count of 0, i.e., (2, 0) is inserted in the queue.- A set containing visited buses is also created.

1 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Queue (2,1) (5,1) (7,1) Visited Buses 0 Station: 2 Buses Taken: 0 ------------------------------------------------------ - Dequeue an element (2, 0) from the queue, and store the values in Station and Buses Taken.- Get the bus number (0) of Station (2) from the adjacency list, and add in Visited Buses.- Traverse all stations of bus (0), and enqueue them along with Buses Taken + 1, i.e., (2, 1), (5, 1), and (7, 1), into the queue.

2 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Visited Buses 0 Queue (5,1) (7,1) Station: 2 Buses Taken: 1 ------------------------------------------------------ - Dequeue an element (2, 1) from the queue, and store the values in Station and Buses Taken.- Get the bus number (0) of Station (2) from adjacency list.- 0 is already present in the Visited Buses and there are no more buses passing to this station Therefore, we move to the next iteration.

3 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Visited Buses 0 Buses Taken: 1 Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Queue (7,1) Station: 5 ------------------------------------------------------ - Dequeue an element (5, 1) from the queue, and store the values in Station and Buses Taken.- Get the bus number (0) of Station (5) from adjacency list.- 0 is already present in the Visited Buses and there are no more buses passing to this station. Therefore, we move to the next iteration.

4 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Visited Buses 0 Buses Taken: 1 Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Station: 7 Queue ------------------------------------------------------ - Dequeue an element (7, 1) from the queue, and store the values in Station and Buses Taken.- Get the bus number (0) of Station (7) from adjacency list.- 0 is already present in the Visited Buses. Now, there is another bus (1) passing from this station. Therefore, we iterate for that bus.

5 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Buses Taken: 1 Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Station: 7 Queue (4,2) (6,2) (7,2) Visited Buses 0 1 ------------------------------------------------------ - Another bus (1) is passed from the station (7). Get that adjacency list.- 1 is not present in the Visited Buses. Add 1 into Visited Buses.- Traverse all stations of bus (1), and enqueue them along with Buses Taken + 1, i.e., (4, 2), (6, 2), and (7, 2), into the queue.

6 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Visited Buses 0 1 Station: 4 Buses Taken: 2 Queue (6,2) (7,2) Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 ------------------------------------------------------ - Dequeue an element (4, 2) from the queue, and store the values in Station and Buses Taken.- Get the bus number (1) of Station (4) from adjacency list.- 1 is already present in the Visited Buses and there are no more buses passing to this station. Therefore, we move to the next iteration.

7 of 8

Created with Fabric.js 3.6.6 src: 2 dest: 6 Bus Routes 2 5 7 4 6 7 Graph Adjacency List Visited Buses 0 1 Buses Taken: 2 Station Bus Number 2 0 5 0 7 0, 1 4 1 6 1 Queue (7,2) Station: 6 ------------------------------------------------------ - Dequeue an element (6, 2) from the queue, and store the values in Station and Buses Taken.- Since the station (6) is equal to the destination (6), return Buses Taken (2).

8 of 8

Let’s look at the code for this solution below:

Bus Routes

Time complexity#

The time complexity of this solution is O(R×S)O(R \times S), where RR is the total number of routes and SS is the number of stations.

Space complexity#

We are using an adjacency list, queue, and visited buses set as additional memory. So, the space complexity of the algorithm is O(R×S)O(R \times S), where RR is the total number of routes, and SS is the number of stations.

Bus Routes

Trie: Introduction