LeetCode 815 - Bus Routes

LeetCode Problem 815

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Breadth-First Search

Solution

Problem Understanding

This problem asks us to determine the minimum number of buses required to travel from a given starting bus stop (source) to a destination bus stop (target) given a set of bus routes. Each route is represented as a list of bus stops that a particular bus cycles through indefinitely. For example, if routes[0] = [1,5,7], the bus repeatedly goes from stop 1 to 5 to 7 and back to 1.

The input consists of a 2D array routes, an integer source, and an integer target. The expected output is an integer representing the fewest buses needed to reach the destination or -1 if it is impossible.

Constraints inform us about the problem scale: the number of routes is up to 500, each route can have up to 105 stops, and the total number of stops across all routes does not exceed 105. Each stop is a non-negative integer less than 10^6, and all stops within a single route are unique. This suggests that a brute-force approach that tries all stop-to-stop paths directly will be too slow; a more efficient method is necessary. Edge cases include the scenario where source equals target (requiring 0 buses), or routes that do not intersect with the source or target (requiring a -1 result).

Approaches

The brute-force approach would attempt to traverse from source to target by exploring all possible bus stop sequences. This could involve recursively checking every possible bus route transfer at every stop. While this would produce the correct answer, it is computationally prohibitive because of the large number of stops and routes, potentially resulting in exponential time complexity.

The optimal approach relies on representing the problem as a graph traversal. Instead of treating stops individually, we can treat buses as nodes. Two buses are connected if they share at least one common stop. We also maintain a mapping from each stop to all buses that visit it. Using this, we can perform a breadth-first search (BFS) starting from all buses that include the source stop. At each BFS level, we increment the number of buses taken. When we encounter a bus that reaches the target stop, we return the current level as the answer.

Algorithm Walkthrough

1. If source equals target, immediately return 0 because no buses are needed.
2. Build a mapping from each bus stop to all buses that visit that stop. This allows us to quickly identify which buses we can take from any stop.
3. Construct a graph where each node represents a bus and an edge exists between two buses if they share a common stop. This represents possible bus transfers.
4. Initialize a BFS queue with all buses that include the source stop. Track visited buses to avoid cycles.
5. Perform BFS level by level. At each level, increment a counter representing the number of buses taken so far.
6. For each bus in the current level, check if it reaches the target. If yes, return the current bus count.
7. Otherwise, enqueue all unvisited buses connected to the current bus and mark them as visited.
8. If BFS completes without finding a bus that reaches the target, return -1 because the target is unreachable.

Why it works: This algorithm guarantees the minimum number of buses because BFS explores all possible paths level by level. The first time we reach a bus containing the target stop, we have used the fewest possible transfers.

Python Solution

from collections import defaultdict, deque
from typing import List, Set

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        if source == target:
            return 0
        
        stop_to_buses = defaultdict(set)
        for bus_index, stops in enumerate(routes):
            for stop in stops:
                stop_to_buses[stop].add(bus_index)
        
        bus_graph = [set() for _ in range(len(routes))]
        for stop, buses in stop_to_buses.items():
            buses = list(buses)
            for i in range(len(buses)):
                for j in range(i + 1, len(buses)):
                    bus_graph[buses[i]].add(buses[j])
                    bus_graph[buses[j]].add(buses[i])
        
        start_buses = stop_to_buses[source]
        target_buses = stop_to_buses[target]
        
        queue = deque([(bus, 1) for bus in start_buses])
        visited_buses: Set[int] = set(start_buses)
        
        while queue:
            bus, buses_taken = queue.popleft()
            if bus in target_buses:
                return buses_taken
            for neighbor in bus_graph[bus]:
                if neighbor not in visited_buses:
                    visited_buses.add(neighbor)
                    queue.append((neighbor, buses_taken + 1))
        
        return -1

Explanation: The Python solution first maps stops to buses and builds a graph of buses connected by shared stops. BFS is initiated from all buses containing the source. Each BFS level represents taking an additional bus. We return the level when we first encounter a bus containing the target. Visited buses are tracked to avoid redundant exploration.

Go Solution

package main

func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target {
        return 0
    }

    stopToBuses := make(map[int][]int)
    for i, stops := range routes {
        for _, stop := range stops {
            stopToBuses[stop] = append(stopToBuses[stop], i)
        }
    }

    busGraph := make([]map[int]struct{}, len(routes))
    for i := range busGraph {
        busGraph[i] = make(map[int]struct{})
    }

    for _, buses := range stopToBuses {
        for i := 0; i < len(buses); i++ {
            for j := i + 1; j < len(buses); j++ {
                busGraph[buses[i]][buses[j]] = struct{}{}
                busGraph[buses[j]][buses[i]] = struct{}{}
            }
        }
    }

    startBuses := stopToBuses[source]
    targetBuses := make(map[int]struct{})
    for _, b := range stopToBuses[target] {
        targetBuses[b] = struct{}{}
    }

    queue := make([][2]int, 0)
    visited := make(map[int]struct{})
    for _, b := range startBuses {
        queue = append(queue, [2]int{b, 1})
        visited[b] = struct{}{}
    }

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        bus, busesTaken := current[0], current[1]
        if _, ok := targetBuses[bus]; ok {
            return busesTaken
        }
        for neighbor := range busGraph[bus] {
            if _, ok := visited[neighbor]; !ok {
                visited[neighbor] = struct{}{}
                queue = append(queue, [2]int{neighbor, busesTaken + 1})
            }
        }
    }

    return -1
}

Explanation: The Go implementation mirrors the Python logic. Maps replace sets where necessary. BFS is performed using a slice queue. The graph of buses is represented with maps for adjacency. The algorithm efficiently finds the minimum buses needed.

Worked Examples

Example 1: routes = [[1,2,7],[3,6,7]], source = 1, target = 6

Example 2: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12

Complexity Analysis

The total complexity is manageable due to the problem constraints. Although R^