1145HardArrayDynamic ProgrammingDepth-First SearchGraph TheoryTopological SortKosaraju's AlgorithmTarjan's SCC Algorithm

Seating Staff Beside the One They Named

Tracked in this browser only

Write code

Trains the technique from

LeetCode 2127Maximum Employees to Be Invited to a Meeting

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.

Each of n staff, numbered 0 through n - 1, names exactly one other member of staff in pick, and nobody names themselves.

The staff are to be seated round one round table. A member of staff will only sit down if the person they named ends up seated directly beside them, on either side.

Return the largest number of staff that can be seated.

Examples

Example 1

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

Staff 0 and 1 name each other, so they sit side by side. Staff 2 named 1 and staff 3 named 2, so those two line up outwards from the pair and all four are seated.

Example 2

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

The five name each other round in a ring, so seating them in that order puts everyone beside the person they named.

Example 3

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

Two separate pairs name each other. Each pair sits together and the two pairs take different stretches of the table, so all four are seated.

Constraints

2 <= pick.length <= 10^5
0 <= pick[i] <= pick.length - 1
pick[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 maximum_invitations(pick: list[int]) -> int:

Java

public int maximumInvitations(int[] pick)

The intended approach

Time O(n) over the staff.Space O(n) for the chain lengths and the peeling.

Following the names from anyone leads eventually into a ring, since everybody names exactly one person. Those rings are the only structures that can seat themselves, and everyone else hangs off a ring in a chain. A ring of three or more has to take the whole table: seated in ring order everyone has the person they named on one side, and nobody else can squeeze in, because inserting anyone would break the two neighbours apart. So such a ring seats exactly its own size and nothing more. A ring of two is different. The pair sit beside each other, each with the other on one side and a free neighbour on the other, so a chain of staff leading into one of the pair can line up outwards from them, each one beside the person they named. That means a pair seats itself plus the longest chain feeding into each of its two members. And because such a group takes only a stretch of the table rather than the whole ring, several pairs can be seated at once, so their totals add up. Peeling the staff nobody names, over and over, strips the chains away and measures how long the chain into each member is on the way. Whatever survives the peeling is exactly the rings. The answer is the larger of the longest ring of three or more and the total across all the pairs.

Pythonentry point: maximum_invitations

def maximum_invitations(pick):
    from collections import deque
    n = len(pick)
    incoming = [0] * n
    for target in pick:
        incoming[target] += 1
    queue = deque()
    for i in range(n):
        if incoming[i] == 0:
            queue.append(i)
    depth = [1] * n
    gone = [False] * n
    while queue:
        node = queue.popleft()
        gone[node] = True
        nxt = pick[node]
        if depth[node] + 1 > depth[nxt]:
            depth[nxt] = depth[node] + 1
        incoming[nxt] -= 1
        if incoming[nxt] == 0:
            queue.append(nxt)
    longest = 0
    paired = 0
    for i in range(n):
        if gone[i]:
            continue
        size = 0
        node = i
        while not gone[node]:
            gone[node] = True
            size += 1
            node = pick[node]
        if size == 2:
            paired += depth[i] + depth[pick[i]]
        elif size > longest:
            longest = size
    return longest if longest > paired else paired

The obvious version

Try to seat people outright. Working from the largest group down, take every choice of that many staff and every way of arranging them round the table, and check that each one of them has the person they named on one side or the other. The first group size that works is the answer. Costs the factorial of the group size for every choice of group.

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_maximum_invitations(pick):
    from itertools import combinations, permutations
    n = len(pick)
    for size in range(n, 1, -1):
        for members in combinations(range(n), size):
            head = members[0]
            for tail in permutations(members[1:]):
                seats = [head] + list(tail)
                ok = True
                for at in range(size):
                    left = seats[at - 1]
                    right = seats[(at + 1) % size]
                    want = pick[seats[at]]
                    if want != left and want != right:
                        ok = False
                        break
                if ok:
                    return size
    return 0

How this problem was checked

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