Bus Routes

Table of Contents +

You want the fewest bus rides from your stop to your destination. Each bus runs a fixed loop of stops. The catch is what counts as one step. A single bus can carry you across many stops at once. So the smart move is to count buses, not stops.

🎯 The Problem

You want the fewest buses from a start stop to a target stop. Here are the rules.

You get a list of routes. Each route is a list of stops one bus visits in a loop.
You also get a start stop and a target stop.
Return the fewest number of buses you must take from start to target.
One bus can carry you across many stops. So you count buses, not stops.
If it is impossible, return -1.
If start already equals target, you need zero buses.

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

Output: 2

Explanation:
  Take the first bus from stop 1 to stop 7. That is one bus.
  Stop 7 is also on the second bus. Take it from 7 to 6. That is the second bus.
  So the answer is 2.

Here is the map. Two buses share stop 7, which is the place where you can change buses.

🐢 Approach 1: BFS Over Stops (Brute Force)

The first instinct is to treat each stop as a node and search stop by stop.

The idea:

Make each stop a node in a graph.
Connect two stops if a bus visits both.
Run breadth-first search from the start stop.

Why it is weak:

Breadth-first search, or BFS, explores level by level. So one level is one stop hop.
But one bus carries you across many stops at once.
So this counts stops crossed, not buses boarded. Wrong number.
You also link every pair of stops on a route. That is slow to build.

Here is the stop-level BFS code:

from collections import deque
def num_buses_to_destination(routes, source, target):
    if source == target:
        return 0
    route_sets = [set(r) for r in routes]
    q, seen_stops, used = deque([(source, 0)]), {source}, set()
    while q:
        stop, buses = q.popleft()
        for i, route in enumerate(route_sets):
            if i in used or stop not in route:
                continue
            used.add(i)
            for nxt in route:
                if nxt == target:
                    return buses + 1
                if nxt not in seen_stops:
                    seen_stops.add(nxt); q.append((nxt, buses + 1))
    return -1

🚌 Approach 2: BFS Over Routes (Best)

The idea in one line: make the unit of search a whole bus, so one BFS level means one more bus boarded.

The idea:

The queue holds routes, not stops.
One BFS level equals one bus.
Build a map from each stop to the routes through it. Call it stopToRoutes.

How it works:

Board every route that passes through the source. That is level one, one bus so far.
For each route in the queue, scan all its stops.
If any stop is the target, return the current bus count.
From each stop, find every other route through it. Those are transfers.
Add the unvisited routes to the next level.
Mark routes visited so you never board the same bus twice.
After a full level, add one to the bus count.

Why it is fast:

Each route enters the queue once.
One level is one bus, so the first time you reach the target the count is correct.

Here is the BFS, one level at a time, for the example.

Steps to Solve

If source equals target, return 0.
Build a map from each stop to the list of routes that include it.
Put every route through the source into a queue. Mark those routes visited. Set buses to 1.
Process the queue one level at a time. For each route, scan its stops.
If a stop is the target, return the current bus count.
For each stop, add every unvisited route through it to the next level. After a full level, add one to the bus count.
If the queue empties without reaching the target, return -1.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version builds a stop-to-routes dictionary and runs a BFS over routes using a deque, one level per bus.

from collections import deque, defaultdict


def num_buses_to_destination(routes, source, target):
    if source == target:
        return 0

    stop_to_routes = defaultdict(list)       # stop -> routes passing through it
    for i, route in enumerate(routes):
        for stop in route:
            stop_to_routes[stop].append(i)

    queue = deque()
    visited_route = set()
    for r in stop_to_routes[source]:         # board every route through source
        queue.append(r)
        visited_route.add(r)

    buses = 1
    while queue:
        for _ in range(len(queue)):          # process one whole level
            ri = queue.popleft()
            for stop in routes[ri]:
                if stop == target:           # this bus reaches the target
                    return buses
                for nxt in stop_to_routes[stop]:
                    if nxt not in visited_route:
                        visited_route.add(nxt)
                        queue.append(nxt)
        buses += 1                           # finished a level, one more bus
    return -1


routes = [[1, 2, 7], [3, 6, 7]]
print(num_buses_to_destination(routes, 1, 6))

The output of the above code will be:

Let us read the Python version line by line, because the level loop is what counts buses correctly.

The early if source == target: return 0 handles the case where you are already there. No bus needed.

stop_to_routes is the index that makes everything fast. For each route number i and each stop on it, we append i to that stop’s list. So later, given any stop, we instantly know every bus that touches it.

We seed the BFS with every route through the source. Those are the buses you can board first. We mark each as visited so we never board it again. buses starts at 1 because boarding any seed route means you are already on one bus.

The outer while queue runs once per level. The line for _ in range(len(queue)) is the level trick. We freeze the count of routes at this level before we start adding the next level. So everything we process in this inner loop is exactly one bus deep.

For each route we scan its stops. If a stop is the target, the current buses value is the answer, because this route is reachable at this depth.

Otherwise, for each stop we look up every other route through it and add the unvisited ones. Those are transfers, the next level of buses.

After the inner loop finishes a whole level, buses += 1 records that reaching the next level costs one more bus. If the queue empties with no target found, the buses cannot reach it, so we return -1.

⏱️ Time and Space Complexity

Let R be the number of routes and S the total stops across all routes. Building the map is O(S). The BFS visits each route once and scans its stops, and for each stop it looks at the routes through it. In the worst case this is about O(S + transfers). We store the map and the visited set, so space is O(S + R). The key win over BFS-over-stops is that one level now equals one bus, so the count is correct.

Approach	Time Complexity	Space Complexity
BFS over stops (brute force)	O(S²) building links	O(S²)
BFS over routes (best)	O(S + R²) worst case	O(S + R)

Tip

The whole question turns on the unit. A BFS over stops counts stops crossed. A BFS over routes counts buses boarded. The problem asks for buses, so the queue must hold routes.

🧩 Key Takeaways

✅ Count buses, not stops. One BFS level must equal one bus boarded.
✅ Build a stop-to-routes map so you instantly know which buses touch a stop.
✅ Seed the queue with every route through the source, and start the count at 1.
✅ Mark routes visited so you never board the same bus twice.
✅ Handle source equal to target up front, returning 0.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Evaluate Division
Making a Large Island

Previous All Ancestors of a Node in a Directed Acyclic Graph Next Number of Islands II

Bus Routes

Follow Us

Follow Us