We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Bus Routes

Difficulty: Hard

Problem Description

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats 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.

Key Insights

  • Each bus route can be viewed as a graph where bus stops are nodes and routes are edges.
  • BFS (Breadth-First Search) is a suitable algorithm to find the shortest path in an unweighted graph.
  • A mapping of bus stops to bus routes can optimize the search process by allowing quick access to all routes that serve a particular bus stop.

Space and Time Complexity

Time Complexity: O(N + E), where N is the number of bus stops and E is the number of edges (connections between stops via buses).
Space Complexity: O(N + R), where R is the total number of bus routes, for storing the graph representation and the queue during BFS.

Solution

We can solve this problem using a graph traversal approach, specifically using Breadth-First Search (BFS). The steps are as follows:

  1. Graph Construction: Create a mapping from bus stops to bus routes. Each bus stop will point to all the bus routes that pass through it.
  2. BFS Initialization: Start from the source bus stop and initialize a queue to explore the bus routes. Keep track of visited bus routes to avoid processing the same route multiple times.
  3. BFS Traversal: For each bus stop, check if it matches the target. If it does, return the number of buses taken. If not, enqueue all the bus routes that can be accessed from the current bus stop and mark them as visited.
  4. End Condition: If the queue is exhausted and the target is not reached, return -1.

Code Solutions

from collections import defaultdict, deque

def numBusesToDestination(routes, source, target):
    if source == target:
        return 0
    
    stop_to_routes = defaultdict(list)
    
    # Build the stop to routes mapping
    for i, route in enumerate(routes):
        for stop in route:
            stop_to_routes[stop].append(i)
    
    visited_stops = set()
    visited_routes = set()
    queue = deque([(source, 0)])  # (current stop, number of buses taken)
    
    while queue:
        current_stop, buses_taken = queue.popleft()
        
        # Check all routes from current stop
        for route_index in stop_to_routes[current_stop]:
            if route_index in visited_routes:
                continue
            visited_routes.add(route_index)
            
            # Check all stops in this route
            for stop in routes[route_index]:
                if stop == target:
                    return buses_taken + 1
                if stop not in visited_stops:
                    visited_stops.add(stop)
                    queue.append((stop, buses_taken + 1))
    
    return -1
← Back to All Questions