Bus Routes
Problem Description
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 the0thbus travels in the sequence1 -> 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 = 12Output: -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
Solve it on LeetCode
Approaches
1. Breadth-First Search (BFS)
Intuition:
This problem can be visualized as finding the shortest path in an unweighted graph. Each route can be considered as a node, and there is an edge between two nodes if they share at least one bus stop. The task is to determine the minimum number of buses needed to travel from the source to the target. Here’s the breakdown:
- Graph Representation: Use each route as a node. Routes are connected if they share a common bus stop.
- BFS Traversal: Utilize BFS to ensure the minimum transfer path is found.
- Starting Points: Begin from all the routes that contain the
source. - Destination Condition: Stop when any route containing the
targetis reached in the BFS traversal.
Code:
- Time Complexity: O(N + S) where N is the total number of bus routes and S is the total number of bus stops. Each stop to route association is examined once.
- Space Complexity: O(N + S). We store mappings for each stop to their corresponding routes and a visited list for routes.