LeetCode 0815. Bus Routes Solution in Java, C++, Python & More | Explanation + Code

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 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

Solutions

Solution 1: BFS

First, we check if source and target are the same. If they are, we directly return 0.

Next, we use a hash table g to build a mapping from stops to bus routes. For each bus route, we traverse all the stops it passes through and map each stop to that bus route, i.e., g[stop] represents all bus routes passing through stop stop.

Then, we check if source and target are in the stop mapping. If they are not, we return -1.

We use a queue q to perform a breadth-first search (BFS). Each element in the queue is a tuple (stop, busCount), representing the current stop stop and the number of buses taken to reach the current stop busCount.

We initialize a set visBus to record the bus routes that have been visited and a set visStop to record the stops that have been visited. Then, we add source to visStop and (source, 0) to the queue q.

Next, we start the BFS. While the queue q is not empty, we take out the first element from the queue, which is the current stop stop and the number of buses taken to reach the current stop busCount.

If the current stop stop is the target stop target, we return the number of buses taken to reach the target stop busCount.

Otherwise, we traverse all bus routes passing through the current stop. For each bus route, we traverse all stops on that route. If a stop nextStop has not been visited, we add it to visStop and add (nextStop, busCount + 1) to the queue q.

Finally, if we cannot reach the target stop, we return -1.

The time complexity is O(L), and the space complexity is O(L), where L is the total number of stops on all bus routes.

PythonJavaC++GoTypeScriptC#

class Solution: def numBusesToDestination( self, routes: List[List[int]], source: int, target: int ) -> int: if source == target: return 0 g = defaultdict(list) for i, route in enumerate(routes): for stop in route: g[stop].append(i) if source not in g or target not in g: return -1 q = [(source, 0)] vis_bus = set() vis_stop = {source} for stop, bus_count in q: if stop == target: return bus_count for bus in g[stop]: if bus not in vis_bus: vis_bus.add(bus) for next_stop in routes[bus]: if next_stop not in vis_stop: vis_stop.add(next_stop) q.append((next_stop, bus_count + 1)) return -1(code-box)

class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } Map<Integer, List<Integer>> g = new HashMap<>(); for (int i = 0; i < routes.length; i++) { for (int stop : routes[i]) { g.computeIfAbsent(stop, k -> new ArrayList<>()).add(i); } } if (!g.containsKey(source) || !g.containsKey(target)) { return -1; } Deque<int[]> q = new ArrayDeque<>(); Set<Integer> visBus = new HashSet<>(); Set<Integer> visStop = new HashSet<>(); q.offer(new int[] {source, 0}); visStop.add(source); while (!q.isEmpty()) { int[] current = q.poll(); int stop = current[0], busCount = current[1]; if (stop == target) { return busCount; } for (int bus : g.get(stop)) { if (visBus.add(bus)) { for (int nextStop : routes[bus]) { if (visStop.add(nextStop)) { q.offer(new int[] {nextStop, busCount + 1}); } } } } } return -1; } }(code-box)

class Solution { public: int numBusesToDestination(vector<vector<int>>& routes, int source, int target) { if (source == target) { return 0; } unordered_map<int, vector<int>> g; for (int i = 0; i < routes.size(); i++) { for (int stop : routes[i]) { g[stop].push_back(i); } } if (!g.contains(source) || !g.contains(target)) { return -1; } queue<pair<int, int>> q; unordered_set<int> visBus; unordered_set<int> visStop; q.push({source, 0}); visStop.insert(source); while (!q.empty()) { auto [stop, busCount] = q.front(); q.pop(); if (stop == target) { return busCount; } for (int bus : g[stop]) { if (!visBus.contains(bus)) { for (int nextStop : routes[bus]) { if (!visStop.contains(nextStop)) { visBus.insert(bus); visStop.insert(nextStop); q.push({nextStop, busCount + 1}); } } } } } return -1; } };(code-box)

func numBusesToDestination(routes [][]int, source int, target int) int { if source == target { return 0 } g := make(map[int][]int) for i, route := range routes { for _, stop := range route { g[stop] = append(g[stop], i) } } if g[source] == nil || g[target] == nil { return -1 } q := list.New() q.PushBack([2]int{source, 0}) visBus := make(map[int]bool) visStop := make(map[int]bool) visStop[source] = true for q.Len() > 0 { front := q.Front() q.Remove(front) stop, busCount := front.Value.([2]int)[0], front.Value.([2]int)[1] if stop == target { return busCount } for _, bus := range g[stop] { if !visBus[bus] { visBus[bus] = true for _, nextStop := range routes[bus] { if !visStop[nextStop] { visStop[nextStop] = true q.PushBack([2]int{nextStop, busCount + 1}) } } } } } return -1 }(code-box)

function numBusesToDestination(routes: number[][], source: number, target: number): number { if (source === target) { return 0; } const g: Map<number, number[]> = new Map(); for (let i = 0; i < routes.length; i++) { for (const stop of routes[i]) { if (!g.has(stop)) { g.set(stop, []); } g.get(stop)!.push(i); } } if (!g.has(source) || !g.has(target)) { return -1; } const q: [number, number][] = [[source, 0]]; const visBus: Set<number> = new Set(); const visStop: Set<number> = new Set([source]); for (const [stop, busCount] of q) { if (stop === target) { return busCount; } for (const bus of g.get(stop)!) { if (!visBus.has(bus)) { visBus.add(bus); for (const nextStop of routes[bus]) { if (!visStop.has(nextStop)) { visStop.add(nextStop); q.push([nextStop, busCount + 1]); } } } } } return -1; }(code-box)

public class Solution { public int NumBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } // Use Dictionary to map stops to bus routes var g = new Dictionary<int, List<int>>(); for (int i = 0; i < routes.Length; i++) { foreach (int stop in routes[i]) { if (!g.ContainsKey(stop)) { g[stop] = new List<int>(); } g[stop].Add(i); } } // If source or target is not in the mapping, return -1 if (!g.ContainsKey(source) || !g.ContainsKey(target)) { return -1; } // Initialize queue and visited sets var q = new Queue<int[]>(); var visBus = new HashSet<int>(); var visStop = new HashSet<int>(); q.Enqueue(new int[] { source, 0 }); visStop.Add(source); // Begin BFS while (q.Count > 0) { var current = q.Dequeue(); int stop = current[0], busCount = current[1]; // If the current stop is the target stop, return the bus count if (stop == target) { return busCount; } // Traverse all bus routes passing through the current stop foreach (int bus in g[stop]) { if (visBus.Add(bus)) { // Traverse all stops on this bus route foreach (int nextStop in routes[bus]) { if (visStop.Add(nextStop)) { q.Enqueue(new int[] { nextStop, busCount + 1 }); } } } } } return -1; // If unable to reach the target stop, return -1 } }(code-box)