0496MediumBacktrackingDepth-First SearchBreadth-First SearchGraph TheoryDirected Acyclic Graph

Parcel Routes Through the Hubs

Tracked in this browser only

Trains the technique from

LeetCode 797All Paths From Source to Target

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A courier network runs n sorting hubs, numbered 0 through n - 1, where n is the length of links. The entry links[i] lists every hub that a parcel resting at hub i may be forwarded to. Forwarding works only in the direction listed, and the belts are laid out so that a parcel can never come back to a hub it has already left.

Parcels enter at hub 0 and leave from hub n - 1. A route is the run of hubs one parcel passes through on its way, written down in visiting order, with hub 0 first and hub n - 1 last. Two routes are different when their runs of hubs differ.

Return every route a parcel could take. The routes themselves may come back in any order, but the hubs inside each route must stay in visiting order. If nothing forwarded from hub 0 ever lands on hub n - 1, return an empty list.

Examples

Example 1

Input: links = [[2, 1], [3, 4], [3], [5], [5], []]
Output: [[0, 2, 3, 5], [0, 1, 3, 5], [0, 1, 4, 5]]

Hub 0 forwards to hub 2 and to hub 1, and each of the three answers listed runs from hub 0 to hub 5 using only forwardings named in `links`, for instance hub 0 to hub 1 to hub 4 to hub 5.

Example 2

Input: links = [[1, 2], [], [4], [4], []]
Output: [[0, 2, 4]]

Hub 1 forwards nowhere, so a parcel sent there stays put and that run of hubs is not a route. The single route ends on hub 4.

Example 3

Input: links = [[4, 2], [4], [1], [], []]
Output: [[0, 4], [0, 2, 1, 4]]

Hub 0 forwards straight to hub 4, and it also forwards to hub 2, from where a parcel reaches hub 4 by way of hub 1.

Constraints

n == links.length
2 <= n <= 15
0 <= links[i][j] < n
links[i][j] != i, so no hub forwards to itself
The entries of links[i] are distinct
Following the belts can never return a parcel to an earlier hub

The values you return may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def hub_routes(links: list[list[int]]) -> list[list[int]]:

Java

public List<List<Integer>> hubRoutes(int[][] links)

The intended approach

Time O(n * 2^n) worst case: that many routes can exist and each is copied in O(n).Space O(n) for the route being grown and its cursors, plus the space held by the returned routes.

Grow one route at a time from hub 0, keeping the hubs visited so far in a list and, alongside it, how far through each of those hubs' forwarding lists the walk has got. When the list ends on the last hub a copy is recorded; when a hub's forwarding list runs out the hub is dropped and the walk carries on from the hub before it. Because the belts never loop, the same list can be reused for every route, and the stack of cursors keeps the walk iterative rather than recursive.

Pythonentry point: hub_routes

def hub_routes(links):
    # depth-first walk driven by an explicit stack, so a chain of every hub is safe
    last = len(links) - 1
    routes = []
    path = [0]
    cursor = [0]           # cursor[d] is the next forwarding to try from path[d]
    while path:
        here = path[-1]
        if here == last:
            routes.append(list(path))
            path.pop()
            cursor.pop()
            continue
        i = cursor[-1]
        if i == len(links[here]):
            path.pop()
            cursor.pop()
            continue
        cursor[-1] = i + 1
        path.append(links[here][i])
        cursor.append(0)
    return routes

The obvious version

Breadth-first: hold every partial route of the current length, extend each one by every forwarding available at its tail, and set aside any that has reached the last hub. Repeats until no partial route is left.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_hub_routes(links):
    last = len(links) - 1
    frontier = [[0]]
    routes = []
    while frontier:
        following = []
        for route in frontier:
            tail = route[-1]
            if tail == last:
                routes.append(route)
                continue
            for step in links[tail]:
                following.append(route + [step])
        frontier = following
    return routes

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in