Show problems as
Classic problem #2127HardArrayDynamic ProgrammingDepth-First SearchGraph TheoryTopological SortKosaraju's AlgorithmTarjan's SCC Algorithm

Maximum Employees to Be Invited to a Meeting

Real-world version: Seating Staff Beside the One They Named
Tracked in this browser only
Read Maximum Employees to Be Invited to a Meeting on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_invitations(pick: list[int]) -> int:
Java
public int maximumInvitations(int[] pick)

More on the same topics