0666HardDepth-First SearchBreadth-First SearchGraph TheoryTopological SortKosaraju's AlgorithmTarjan's SCC Algorithm

Longest Loop in a Relay Network

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 packet network has stations numbered 0 to n - 1. Each station hands every packet it receives to at most one other station: forward[i] is the station that station i hands to, and forward[i] = -1 means station i keeps what it receives and hands on nothing. No station hands to itself.

A loop is a list of distinct stations s[0], s[1], ..., s[L-1] with L >= 2 where each station hands to the next one, forward[s[j]] = s[j + 1] for every j below L - 1, and the last hands back to the first, forward[s[L-1]] = s[0]. The length of that loop is L, the number of stations on it.

Return the length of the longest loop in the network, or -1 if no loop exists.

Examples

Example 1

Input: forward = [1, 0, 3, 4, 2, 6, -1]
Output: 3

Stations `2, 3, 4` hand on in a ring, which is a loop of three. Stations `0` and `1` hand to each other, a loop of two. Station `5` hands to `6`, which hands on nothing.

Example 2

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

Stations `3, 4, 5` form a loop of three. Stations `0, 1, 2` lead into it but nothing hands back to them, so they are on no loop.

Example 3

Input: forward = [1, 2, 3, 4, -1]
Output: -1

Every packet travels forward to station `4` and stops there. No station is ever handed back to, so there is no loop and the sentinel is returned.

Constraints

2 <= forward.length <= 10^5
-1 <= forward[i] < forward.length
forward[i] != i

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 longest_relay_loop(forward: list[int]) -> int:

Java

public int longestRelayLoop(int[] forward)

The intended approach

Time O(n): every station is stamped once and every hand-off is followed once.Space O(n) for the walk id and position stamps.

Because every station hands on to at most one other, each walk is forced. Sweep the stations and start a fresh walk from any station not stamped yet, giving the walk its own id and stamping each station it visits with that id and with its position in the walk. A walk stops when it reaches a station that hands on nothing or one already stamped. If the station it stopped on carries the current walk's id, the difference between the current position and that station's recorded position is a loop length; keep the largest. Because a station is stamped once, the whole sweep touches each station a constant number of times.

Pythonentry point: longest_relay_loop

def longest_relay_loop(forward):
    # one sweep: stamp every station with the id of the walk that first reached it
    n = len(forward)
    walk_of = [0] * n
    step_of = [0] * n
    walk = 0
    best = -1
    for start in range(n):
        if walk_of[start]:
            continue
        walk += 1
        node = start
        step = 0
        while node != -1 and walk_of[node] == 0:
            walk_of[node] = walk
            step_of[node] = step
            step += 1
            node = forward[node]
        if node != -1 and walk_of[node] == walk:
            length = step - step_of[node]
            if length > best:
                best = length
    return best

The obvious version

Start a separate walk from every station, recording the step at which each station was reached in that walk. Stop when the walk reaches a station that hands on nothing or one already seen during this same walk; in the second case the gap between the current step and the recorded step is a loop length. Take the largest over all starts, or the sentinel if none was found.

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_longest_relay_loop(forward):
    best = -1
    for start in range(len(forward)):
        first = {}
        node = start
        step = 0
        while node != -1 and node not in first:
            first[node] = step
            step += 1
            node = forward[node]
        if node != -1:
            length = step - first[node]
            if length > best:
                best = length
    return best

How this problem was checked

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