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
- The natural state space is routes, not stops: riding a route costs 1 bus.
- Build a map from stop to the routes serving it.
- BFS: from a stop, board every unvisited route serving it, then enqueue all stops on that route.
- 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 == targetcase: the answer is 0 buses. - Returning
busesinstead ofbuses + 1when 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.