⚡Flashcard Drill➔
NeetCode #653LC-815HardAdvanced Graphs
← Back to All Problems

#653 · #815 · Bus Routes(公交路线)

📌 Problem Statement & Constraints

You are given routes where routes[i] is the list of stops of bus route i, plus source and target. You start at source and may ride any route; each new route counts as one bus. Return the minimum number of buses, or -1. Constraints: 1 <= routes.length <= 500, total stops <= 10^5, 0 <= source, target < 10^6.

💡 Core Algorithmic Approaches

  1. The natural state space is routes, not stops: riding a route costs 1 bus.
  2. Build a map from stop to the routes serving it.
  3. BFS: from a stop, board every unvisited route serving it, then enqueue all stops on that route.
  4. Marking routes visited is what keeps the search linear.

💻 Benchmark Python3 Implementation

class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        from collections import defaultdict, deque
        if source == target:
            return 0                       # already there
        stop_to_routes = defaultdict(list)
        for i, route in enumerate(routes):
            for s in route:
                stop_to_routes[s].append(i)
        visited_routes = set()
        visited_stops = {source}
        q = deque([(source, 0)])
        while q:
            stop, buses = q.popleft()
            for r in stop_to_routes[stop]:
                if r in visited_routes:
                    continue               # this route was already ridden
                visited_routes.add(r)
                for s in routes[r]:
                    if s == target:
                        return buses + 1   # one more bus
                    if s not in visited_stops:
                        visited_stops.add(s)
                        q.append((s, buses + 1))
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total stops): each route is expanded once.
💾 Space Complexity
O(total stops) for the stop-to-routes map.

⚠️ Interview Pitfalls & Follow-ups

  • BFS over stops: it would count stops instead of buses.
  • Not marking routes visited: the same route could be expanded repeatedly.
  • Forgetting the source == target case: the answer is 0 buses.
  • Returning buses instead of buses + 1 when boarding: boarding a new route costs one bus.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems