0706MediumDepth-First SearchBreadth-First SearchGraph TheoryTopological Sort

Courier Base on the Campus Walkways

Tracked in this browser only

Trains the technique from

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 campus has n buildings numbered 0 through n - 1, joined by covered walkways. The walkways arrive as a list of pairs: walkways[k] = [a, b] means one walkway directly joins building a and building b. There are n - 1 walkways, every building is reachable from every other along them, and no walkway is listed twice, so the campus forms a tree.

An internal courier is to be based in one building. The reach of building h is the number of walkways on the route from h to the building furthest from it, counting walkways along the single route that joins the two.

Return every building whose reach is as small as possible, listed in ascending order. For a campus shaped like this there is always either one such building or two.

Examples

Example 1

Input: n = 7, walkways = [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5], [4, 6]]
Output: [3, 4]

From building 3 the routes reach buildings 0, 1, 2 and 4 across one walkway and buildings 5 and 6 across two, so its reach is 2. From building 4 the routes reach buildings 3, 5 and 6 across one walkway and buildings 0, 1 and 2 across two, so its reach is also 2. Both are reported, in ascending order.

Example 2

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

The campus is a single corridor. From building 2 the furthest buildings are 0 and 4, each two walkways away, so its reach is 2 and it is the only building reported.

Example 3

Input: n = 2, walkways = [[1, 0]]
Output: [0, 1]

Each building is one walkway from the other, so both have reach 1 and both are reported.

Constraints

1 <= n <= 2 * 10^4
walkways.length == n - 1
walkways[i].length == 2
0 <= walkways[i][j] <= 2 * 10^4 - 1
Every walkway entry is a building number, so it is smaller than n.
A walkway never joins a building to itself and no pair of buildings is joined twice.
The walkways connect all n buildings into a single tree.

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 best_courier_bases(n: int, walkways: list[list[int]]) -> list[int]:

Java

public List<Integer> bestCourierBases(int n, int[][] walkways)

The intended approach

Time O(n) for n buildings: each building enters one layer and each walkway is inspected from both ends once.Space O(n) for the adjacency lists, the walkway counts and the layer lists.

Build the adjacency lists and the walkway count of every building, then collect the buildings with a single walkway as the current outer layer. Repeatedly remove that whole layer at once: for each removed building, decrement its neighbours' counts, and any neighbour that drops to a single remaining walkway joins the next layer. Stop when two or fewer buildings have not been removed, and return those, sorted. The loop is driven by an explicit layer list rather than recursion, so a campus laid out as one long corridor is no problem. A campus of a single building is answered directly.

Pythonentry point: best_courier_bases

def best_courier_bases(n, walkways):
    # O(n): strip the outermost buildings layer by layer with an explicit queue,
    # never recursing, until one or two buildings are left.
    if n == 1:
        return [0]
    adj = [[] for _ in range(n)]
    degree = [0] * n
    for a, b in walkways:
        adj[a].append(b)
        adj[b].append(a)
        degree[a] += 1
        degree[b] += 1

    layer = [v for v in range(n) if degree[v] == 1]
    left = n
    while left > 2:
        left -= len(layer)
        nxt = []
        for v in layer:
            degree[v] = 0
            for w in adj[v]:
                if degree[w] > 0:
                    degree[w] -= 1
                    if degree[w] == 1:
                        nxt.append(w)
        layer = nxt
    return sorted(layer)

The obvious version

Run a breadth-first sweep out of every building in turn, record the largest distance each sweep finds, and report every building tied for the smallest of those. Costs a full sweep per building, so it is quadratic, but it measures reach directly from the definition.

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_best_courier_bases(n, walkways):
    adj = [[] for _ in range(n)]
    for a, b in walkways:
        adj[a].append(b)
        adj[b].append(a)
    reach = [0] * n
    for src in range(n):
        dist = [-1] * n
        dist[src] = 0
        queue = [src]
        head = 0
        far = 0
        while head < len(queue):
            v = queue[head]
            head += 1
            for w in adj[v]:
                if dist[w] < 0:
                    dist[w] = dist[v] + 1
                    if dist[w] > far:
                        far = dist[w]
                    queue.append(w)
        reach[src] = far
    smallest = min(reach)
    return [v for v in range(n) if reach[v] == smallest]

How this problem was checked

Reference solution executed against 17 test cases — 17 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