What is the time complexity of LeetCode 2127. Maximum Employees to Be Invited to a Meeting?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2127. Maximum Employees to Be Invited to a Meeting?

The Python solution on this page uses O(n) auxiliary space.

Maximum Employees to Be Invited to a Meeting — LeetCode 2127 Python Solution

HardDepth-First SearchGraphTopological Sort

Problem: #2127
Pattern: Topological Sort
Reading time: 7 min
Source: leetcode.com

The problem

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

Example

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.

Python solution

Python

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        def max_cycle(fa: List[int]) -> int:
            n = len(fa)
            vis = [False] * n
            ans = 0
            for i in range(n):
                if vis[i]:
                    continue
                cycle = []
                j = i
                while not vis[j]:
                    cycle.append(j)
                    vis[j] = True
                    j = fa[j]
                for k, v in enumerate(cycle):
                    if v == j:
                        ans = max(ans, len(cycle) - k)
                        break
            return ans

        def topological_sort(fa: List[int]) -> int:
            n = len(fa)
            indeg = [0] * n
            dist = [1] * n
            for v in fa:
                indeg[v] += 1
            q = deque(i for i, v in enumerate(indeg) if v == 0)
            while q:
                i = q.popleft()
                dist[fa[i]] = max(dist[fa[i]], dist[i] + 1)
                indeg[fa[i]] -= 1
                if indeg[fa[i]] == 0:
                    q.append(fa[i])
            return sum(dist[i] for i, v in enumerate(fa) if i == fa[fa[i]])

        return max(max_cycle(favorite), topological_sort(favorite))

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 2127. Maximum Employees to Be Invited to a Meeting is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2127. Maximum Employees to Be Invited to a Meeting?: LeetCode 2127. Maximum Employees to Be Invited to a Meeting is rated Hard on LeetCode.
What is the time complexity of LeetCode 2127. Maximum Employees to Be Invited to a Meeting?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2127. Maximum Employees to Be Invited to a Meeting?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2127. Maximum Employees to Be Invited to a Meeting cover?: LeetCode 2127. Maximum Employees to Be Invited to a Meeting is tagged Depth-First Search, Graph and Topological Sort on LeetCode.