Bus Routes
Explore how to solve the minimum bus routes problem by applying graph traversal techniques. Understand the use of routes as repeating cycles and learn to determine the shortest number of buses to reach a destination. This lesson sharpens your skills in graph fundamentals and problem-solving patterns essential for coding interviews.
We'll cover the following...
Statement
You are given an array, routes, representing bus routes where routes[i] is a bus route that the 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 there is no route.
Constraints:
-
routes.length -
routes[i].length -
routes[i][j] -
src,dest
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
What is the output if the following input is given?
Bus routes = [[4, 2, 12], [3, 26], [1, 10], [4, 26, 6]]
src = 3
dest = 12
2
3
4
-1
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in main.js in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.
import Queue from "./queue.js";function minimumBuses(matrix, s, d){// Replace this placeholder return statement with your codereturn -1;}export { minimumBuses };