You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.
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 <= 105routes[i] are unique.sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106In this approach, we treat the problem as a graph where each bus route is a node and bus stops are edges connecting these nodes. We will perform a Breadth-First Search (BFS) starting from the source and try to reach the target while counting the number of buses required. The BFS helps in finding the shortest path in terms of the number of bus routes.
This code uses Breadth-First Search (BFS) to explore the given routes. A queue is utilized to manage bus stops, beginning at the source, and systematically visit every possible stop until the target is achieved or all possibilities are exhausted. The unique bus stops and routes are tracked to prevent repetition. When the target stop is reached, the code returns the count of buses needed to reach that spot. If the target is unreachable, it returns -1.
JavaScript
Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route.
Space Complexity: O(N * D) for storing the graph.
For optimization, we can leverage a bidirectional BFS. This technique reduces the breadth by simultaneously exploring from both the source and the target and meeting in the middle. A dual directional expansion can therefore lead to faster convergence in finding the solution.
This C++ implementation uses bidirectional BFS to improve time efficiency by concurrently working from both the forward and backward directions. It alternately expands from the queue with fewer elements, using a shared graph or set to determine intersections, which indicates the optimal path. By operating in both directions, this reduces redundant processing and ensures convergence happens faster compared to one-sided BFS.
Java
Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route.
Space Complexity: O(N * D) for storing the graph and queue data structures.
| Approach | Complexity |
|---|---|
| Graph BFS Approach | Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route. |
| Bidirectional BFS Approach | Time Complexity: O(N * D) where N is the number of buses and D is the largest number of bus stops in any bus route. |
Course Schedule - Graph Adjacency List - Leetcode 207 • NeetCode • 428,818 views views
Watch 9 more video solutions →Practice Bus Routes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor