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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Bus Routes

Number: 833

Difficulty: Hard

Paid? No

Companies: Uber, Microsoft, Google, TikTok, Amazon, Pinterest, PhonePe

Problem Description

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. Starting at a bus stop source, you must determine the least number of buses you need to take to reach the bus stop target. You can only travel by following the bus routes. If it is not possible to reach the target, return -1.

Key Insights

  • Model the problem as a graph where nodes are bus routes.
  • Two bus routes are connected if they share at least one common bus stop.
  • Use a hash map to quickly look up bus routes available at any bus stop.
  • Employ Breadth-First Search (BFS) on the bus routes graph to find the minimum number of bus transfers.
  • Mark visited bus routes and bus stops to avoid redundant work.

Space and Time Complexity

Time Complexity: O(N * L) in the worst-case scenario, where N is the number of bus routes and L is the average number of stops per route. Space Complexity: O(N * L) due to storage of the stop-to-buses mapping and BFS auxiliary data structures.

Solution

We begin by constructing a mapping from each bus stop to the list of buses passing through it. This allows quick retrieval of buses available at a given stop. Starting at the source stop, initialize the BFS queue with all buses that can be boarded at that stop. Then, for each bus route in the queue, inspect each stop along that route. If a stop is the target, return the number of buses taken so far. Otherwise, for each unvisited stop, add all adjacent bus routes (buses that pass through this stop) to the BFS queue with an incremented bus count. Continue until the queue is empty, which means the target cannot be reached.

Code Solutions

from collections import defaultdict, deque

def numBusesToDestination(routes, source, target):
    # If source equals target, no buses are needed.
    if source == target:
        return 0

    # Build mapping: bus stop -> list of bus indices
    stop_to_buses = defaultdict(list)
    for bus_index, stops in enumerate(routes):
        for stop in stops:
            stop_to_buses[stop].append(bus_index)
    
    visited_buses = set()
    visited_stops = set([source])
    queue = deque()
    
    # Initialize queue with all buses that include the source stop.
    for bus in stop_to_buses[source]:
        visited_buses.add(bus)
        queue.append((bus, 1))
    
    # Perform BFS over bus routes.
    while queue:
        current_bus, buses_taken = queue.popleft()
        for stop in routes[current_bus]:
            if stop == target:
                return buses_taken
            if stop not in visited_stops:
                visited_stops.add(stop)
                for neighbor_bus in stop_to_buses[stop]:
                    if neighbor_bus not in visited_buses:
                        visited_buses.add(neighbor_bus)
                        queue.append((neighbor_bus, buses_taken + 1))
    return -1

# Example usage:
# routes = [[1,2,7],[3,6,7]]
# print(numBusesToDestination(routes, 1, 6))
← Back to All Questions