Maximum Employees to Be Invited to a Meeting

Tested Python solution for LeetCode 2127 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 2127, Hard. Topics: Array, Dynamic Programming, Depth-First Search, Graph, Topological Sort. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 20 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2127   # by problem number
lcpy gen -s maximum_employees_to_be_invited_to_a_meeting   # by problem name

​

Problem

A company is organizing a meeting and has a list of <code>n</code> employees, waiting to be invited. They have arranged for a large <strong>circular</strong> table, capable of seating <strong>any number</strong> of employees.</p>

<p>The employees are numbered from <code>0</code> to <code>n - 1</code>. Each employee has a <strong>favorite</strong> person and they will attend the meeting <strong>only if</strong> they can sit next to their favorite person at the table. The favorite person of an employee is <strong>not</strong> themself.</p>

<p>Given a <strong>0-indexed</strong> integer array <code>favorite</code>, where <code>favorite[i]</code> denotes the favorite person of the <code>i^th</code> employee, return <em>the <strong>maximum number of employees</strong> that can be invited to the meeting</em>.

​

Examples

Input: favorite = [2,2,1,2]
Output: 3
Explanation:
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3.

Input: favorite = [1,2,0]
Output: 3
Explanation:
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.

Input: favorite = [3,0,1,4,1]
Output: 4
Explanation:
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.

​

Constraints

• n == favorite.length
• 2 <= n <= 10^5
• 0 <= favorite[i] <= n - 1
• favorite[i] != i

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class Solution:
    # Time: O(n)
    # Space: O(n)
    def maximum_invitations(self, favorite: list[int]) -> int:
        n = len(favorite)
        depth = [1] * n
        indegree = [0] * n
        for fav in favorite:
            indegree[fav] += 1

        # Peel off chain nodes so only cycle nodes keep indegree > 0, recording
        # for each cycle node the longest chain of excluded employees hanging
        # off it (depth counts the cycle node itself).
        queue = deque(i for i in range(n) if indegree[i] == 0)
        in_cycle = [True] * n
        while queue:
            node = queue.popleft()
            in_cycle[node] = False
            nxt = favorite[node]
            depth[nxt] = max(depth[nxt], depth[node] + 1)
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)

        visited = [False] * n
        best_cycle = 0
        pair_total = 0
        for start in range(n):
            if not in_cycle[start] or visited[start]:
                continue
            length = 0
            node = start
            while not visited[node]:
                visited[node] = True
                node = favorite[node]
                length += 1
            if length == 2:
                # Mutual pairs can all sit together if their chains face them.
                pair_total += depth[start] + depth[favorite[start]]
            else:
                best_cycle = max(best_cycle, length)
        return max(best_cycle, pair_total)

​

Complexity

Time	Space
O(n)	O(n)

​

Tags

NeetCode All.