Blind Plus 100 Visualized

#90 · Graphs

Bus Routes

routes[i] is a bus that travels its stops in a loop forever. Starting at stop source (not yet on any bus), return the fewest buses you must take to reach stop target, or −1 if it is impossible.

HardLeetCode
  • Current
  • On path / queued
  • Done
  • Cycle / blocked
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Bipartite stop–bus graph

Stops and buses are two kinds of nodes; a bus is connected to each stop it serves. A trip alternates stop → bus → stop, and the cost is the number of buses, not stops. Breadth-first search on this graph (or on the equivalent bus-to-bus graph) gives the minimum.

Memory layout

A hash map from stop to the list of bus indices, with Σ len(routes[i]) entries in total.

OperationCost
buildO(Σ len(routes[i]))
lookup of buses at a stopO(1) + output

BFS queue / level frontier

The queue holds stops (or buses) in order of the number of buses taken. Processing a bus once visits all its stops, so a bus is "expanded" at most once if we remember it.

Memory layout

A FIFO array, plus visited sets for stops and flags for buses.

OperationCost
push / popO(1)

Why it fits

  • Every ride costs one bus no matter how many stops it spans, so the graph is unweighted in "buses" and BFS finds the minimum.
  • Modelling stops directly would turn each bus into a clique with len² edges; indexing stops → buses keeps the work linear in the input size.
  • Marking buses (not just stops) as used is the key optimisation: a bus visits all its stops the first time it is boarded.

Why alternatives degrade

Dijkstra over stops with weight 1 per hop:
Counts each stop-to-stop hop on the same bus as a separate ride unless the clique edges are used, which costs O(len²) per route.
DFS over routes:
It finds a trip, not the shortest one, without exploring every path.
Dynamic programming over stops:
Stops have no natural order, and the transitions form cycles; BFS handles them naturally.

Four approaches, from naive to production

1 · beginner

BFS over stops, scanning every route

time O(S · R · L)space O(S)

BFS where the state is a stop. To expand a stop, scan all routes, and for each route containing that stop, enqueue every stop of the route (with one more bus).

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    if (source == target) return 0;
    vector<pair<int, int>> queue{{source, 0}};
    unordered_set<int> seen{source};
    for (size_t head = 0; head < queue.size(); head++) {
        auto [stop, buses] = queue[head];
        for (auto& route : routes) {
            if (find(route.begin(), route.end(), stop) == route.end()) continue;
            for (int next : route) {
                if (next == target) return buses + 1;
                if (!seen.count(next)) { seen.insert(next); queue.push_back({next, buses + 1}); }
            }
        }
    }
    return -1;
}

Flaws & bottlenecks

  • Every stop scans every route and each includes() is O(L).
  • The same bus is expanded again from each of its stops.
  • Far too slow for 500 routes of 10⁵ stops.

Interviewer cross-questions

Why is the first arrival at the target optimal?

Say: BFS visits stops in order of the number of buses taken; every stop discovered while expanding one level costs one more bus than the stop that discovered it.

Why not count one per stop passed?

Say: Riding the same bus across many stops costs only one bus. That is why all stops of a route are discovered together.

How do you avoid scanning all routes?

Say: Precompute a map from stop to the buses that serve it.

2 · intermediate

BFS over stops with a stop → buses index

time O(Σ L · avg buses per stop)space O(Σ L)

Build stopRoutes once. When expanding a stop, look up the buses serving it and enqueue every unseen stop of each of those buses.

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    if (source == target) return 0;
    unordered_map<int, vector<int>> stopRoutes;
    for (int r = 0; r < (int)routes.size(); r++) {
        for (int stop : routes[r]) {
            stopRoutes[stop].push_back(r);
        }
    }
    vector<pair<int, int>> queue{{source, 0}};
    unordered_set<int> seen{source};
    for (size_t head = 0; head < queue.size(); head++) {
        auto [stop, buses] = queue[head];
        for (int r : stopRoutes[stop]) {
            for (int next : routes[r]) {
                if (next == target) return buses + 1;
                if (!seen.count(next)) { seen.insert(next); queue.push_back({next, buses + 1}); }
            }
        }
    }
    return -1;
}

Flaws & bottlenecks

  • A bus is expanded again from each of its stops: len² work for a long route.
  • Dense overlaps (many buses share most stops) repeat work heavily.
  • No early exit when a stop's buses were already processed.

Interviewer cross-questions

What is the worst case?

Say: One bus with L stops, each queued once and each re-expanding the same bus: O(L²).

What fixes the repetition?

Say: Mark buses as used when first expanded, since all their stops are queued then.

What is the build cost?

Say: One pass over every (bus, stop) pair: O(Σ L).

3 · advanced

BFS over stops, each bus expanded once

time O(Σ L)space O(Σ L)

Same as before but keep a usedRoute set: skip any bus already expanded. Each bus is processed once, each stop is queued once.

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    if (source == target) return 0;
    unordered_map<int, vector<int>> stopRoutes;
    for (int r = 0; r < (int)routes.size(); r++) {
        for (int stop : routes[r]) {
            stopRoutes[stop].push_back(r);
        }
    }
    vector<pair<int, int>> queue{{source, 0}};
    unordered_set<int> seen{source};
    unordered_set<int> usedRoute;
    for (size_t head = 0; head < queue.size(); head++) {
        auto [stop, buses] = queue[head];
        for (int r : stopRoutes[stop]) {
            if (usedRoute.count(r)) continue;
            usedRoute.insert(r);
            for (int next : routes[r]) {
                if (next == target) return buses + 1;
                if (!seen.count(next)) { seen.insert(next); queue.push_back({next, buses + 1}); }
            }
        }
    }
    return -1;
}

Flaws & bottlenecks

  • Hash sets for stops and buses have overhead; arrays would be faster for dense ids.
  • Returns −1 only after exploring everything reachable.
  • Does not check up front whether source or target appear in any route.

Interviewer cross-questions

Why can a bus be skipped the second time?

Say: On first use every one of its stops was queued with a bus count at least as good as any later discovery.

Where is the answer returned?

Say: The moment we see the target while expanding a bus: buses + 1 is final because BFS levels are monotone.

What if source equals target?

Say: Zero buses: handled before any search.

4 · expert

Level-by-level BFS over buses with early exits

time O(Σ L)space O(Σ L)

Treat each bus as a node. Level k is the set of buses reachable with k buses. Expand each bus's stops once, add the buses at new stops to the next level, and stop as soon as a bus serves the target. Guard source, target and absent stops up front.

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    if (source == target) return 0;
    unordered_map<int, vector<int>> stopRoutes;
    for (int r = 0; r < (int)routes.size(); r++) {
        for (int stop : routes[r]) {
            stopRoutes[stop].push_back(r);
        }
    }
    if (!stopRoutes.count(source) || !stopRoutes.count(target)) return -1;
    vector<char> taken(routes.size(), 0);
    unordered_set<int> seenStop{source};
    vector<int> level = stopRoutes[source];
    for (int r : level) taken[r] = 1;
    int buses = 1;
    while (!level.empty()) {
        vector<int> nextLevel;
        for (int r : level) {
            for (int stop : routes[r]) {
                if (stop == target) return buses;
                if (seenStop.count(stop)) continue;
                seenStop.insert(stop);
                for (int r2 : stopRoutes[stop]) {
                    if (!taken[r2]) { taken[r2] = 1; nextLevel.push_back(r2); }
                }
            }
        }
        level = nextLevel;
        buses++;
    }
    return -1;
}

Flaws & bottlenecks

  • More bookkeeping than the stop-queue versions (levels, flags, two sets).
  • Typed arrays and level lists add code for modest constant-factor gains.
  • Only returns the count; reconstructing the trip needs parent pointers.

Interviewer cross-questions

Why is the returned value just buses?

Say: Level k holds buses reachable with k rides, and we return when a level-k bus serves the target, so the answer is k.

What are the edge cases?

Say: source = target (0), source or target served by no bus (−1), a single bus serving both (1), duplicate stops inside a route, and very large stop numbers (use a hash map, not an array indexed by stop).

How would you return the actual route?

Say: Store for every bus the bus (and stop) it was reached from, and walk the pointers back from the final bus.

Synchronized code walkthrough

Showing: BFS over stops, scanning every route — shares the player above; click any step to jump.

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    if (source == target) return 0;
    vector<pair<int, int>> queue{{source, 0}};
    unordered_set<int> seen{source};
    for (size_t head = 0; head < queue.size(); head++) {
        auto [stop, buses] = queue[head];
        for (auto& route : routes) {
            if (find(route.begin(), route.end(), stop) == route.end()) continue;
            for (int next : route) {
                if (next == target) return buses + 1;
                if (!seen.count(next)) { seen.insert(next); queue.push_back({next, buses + 1}); }
            }
        }
    }
    return -1;
}