#2127

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Maximum Employees to Be Invited to a Meeting

Determine the maximum employees to invite based on favorite adjacency constraints using graph indegree and topological ordering techniques.

depth first search graph topological sort

Problem Statement

A company is planning a round-table meeting with n employees labeled from 0 to n - 1. Each employee has exactly one favorite coworker, and they will attend only if seated directly next to that favorite. The favorite relationship is provided in a 0-indexed array favorite, where favorite[i] indicates the favorite person of employee i and favorite[i] != i. The goal is to calculate the largest possible group of employees that can be invited simultaneously while meeting these seating constraints.

Employees can form cycles and chains based on favorite relationships, which determine seating feasibility. You must account for simple cycles of any length and for two-employee mutual favorites with incoming chains. The challenge is to correctly combine cycle sizes with the longest possible chains leading into two-employee cycles to maximize the total number of attendees.

Examples

Example 1

Input: favorite = [2,2,1,2]

Output: 3

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.

Example 2

Input: favorite = [1,2,0]

Output: 3

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.

Example 3

Input: favorite = [3,0,1,4,1]

Output: 4

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 <= 105
0 <= favorite[i] <= n - 1
favorite[i] != i

Solution Approach

Build the directed graph and indegrees

Construct a graph where each employee points to their favorite. Count indegrees for each node to identify which employees are dependencies versus endpoints of chains. Nodes with zero indegree are starting points for DFS traversal and topological sorting.

Identify cycles and chain contributions

Use DFS to detect cycles in the graph, marking visited nodes. For cycles longer than two, the cycle itself determines attendance. For mutual favorites (two-employee cycles), track the longest incoming chain to each of the two nodes, as extending chains increases the total count for that pair.

Combine cycles and chains for the maximum

Sum all standalone cycle lengths and the extended sizes of two-employee cycles including their chains. Compare the sum of mutual favorite extended chains with the largest single cycle length to determine the overall maximum number of employees that can be seated while satisfying adjacency requirements.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each node is visited once in DFS and during topological sorting. Space complexity is O(n) to store graph edges, indegree counts, and visited status for each employee.

What Interviewers Usually Probe

The problem hints at using graph representation of the favorite array and tracking indegrees.
Interviewers expect recognition of cycles versus chains for seating calculations.
Applying DFS to compute longest chains before combining with cycles demonstrates mastery of topological order in graphs.

Common Pitfalls or Variants

Common pitfalls

Ignoring chain contributions into two-employee mutual favorite cycles, which undercounts the maximum attendees.
Misidentifying cycles due to revisiting nodes without proper visited tracking in DFS.
Summing cycle lengths incorrectly, especially when combining chain-augmented two-node cycles with longer independent cycles.

Follow-up variants

Find the minimum number of employees to remove so that no favorite adjacency constraint is violated.
Determine the maximum number of employees that can be seated for multiple simultaneous round tables using the same favorite array.
Adapt the problem to allow employees to attend if seated next to anyone within two positions of their favorite.

FAQ

What is the main strategy for solving Maximum Employees to Be Invited to a Meeting?

The key is representing favorites as a directed graph, identifying cycles, and applying topological ordering with DFS to count maximum attendees.

How do mutual favorites affect the maximum seating?

Two-employee cycles can be extended by incoming chains, increasing the total count beyond the cycle length alone, which is crucial for maximizing invitations.

Can a cycle longer than two be extended with chains?

No, cycles longer than two cannot be extended with chains because each employee in the cycle already requires adjacent placement, limiting flexibility.

Why is indegree tracking important?

Indegree helps identify starting points for DFS and topological sorting, distinguishing chain nodes from cycle nodes for correct attendee counting.

What common mistakes should be avoided?

Avoid missing chain contributions to two-employee cycles, miscounting cycles, or revisiting nodes improperly during DFS, which can all undercount the maximum.

terminal

Solution

Solution 1: Maximum Cycle in Graph + Longest Chain

We observe that the employee's preference relationship in the problem can be regarded as a directed graph, which can be divided into multiple "base cycle inward trees". Each structure contains a cycle, and each node on the cycle is connected to a tree.

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))

Continue Practicing

#2192 all ancestors of a node in a directed acyclic graph #2246 longest path with different adjacent characters #2328 number of increasing paths in a grid