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.
The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.
Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.
Example 1:
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.
Example 2:
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.
Example 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.length2 <= n <= 1050 <= favorite[i] <= n - 1favorite[i] != iProblem Overview: Each employee chooses one favorite coworker. You must arrange employees around a circular meeting table so every person sits next to their favorite. The goal is to compute the maximum number of employees that can be invited while satisfying this constraint.
The input naturally forms a directed graph where node i points to favorite[i]. Every node has exactly one outgoing edge, which means the graph consists of cycles with trees feeding into those cycles. The key challenge is determining which structures can form valid seating arrangements.
Approach 1: Graph Cycle Detection and Longest Chains (O(n) time, O(n) space)
Model the favorites array as a directed graph and analyze its cycles. Two structures matter: cycles of length greater than two and mutual pairs (two nodes pointing to each other). For cycles longer than two, the entire cycle can sit around the table, so the cycle length becomes a candidate answer. Mutual pairs behave differently: you can extend them with chains of employees leading into each member of the pair.
Use a topological sort with indegree counting to peel away non-cycle nodes and compute the longest chain ending at every node. When you encounter a mutual pair (a, b), combine the longest incoming chain into a and the longest incoming chain into b. Sum these contributions for all mutual pairs and compare the result with the length of the largest cycle found via depth-first search or visitation tracking. The final answer is the maximum of these two cases.
Approach 2: Dynamic Programming on Trees (O(n) time, O(n) space)
Instead of computing chain lengths during topological pruning, explicitly build reverse adjacency lists so each node knows who points to it. For nodes that participate in mutual pairs, treat them as roots of trees and run a DFS-style DP over the incoming edges. The DP computes the maximum depth of a chain that can attach to each node without entering another cycle.
This perspective separates the graph into cycle components and tree components. Cycles are detected first using standard graph traversal. For cycles longer than two, simply take their size. For every two-cycle, run DP on the trees feeding into both nodes and add the best chain lengths. The DP approach is conceptually clean because tree depths are computed independently and reused.
Recommended for interviews: The cycle-detection plus topological pruning approach is what most interviewers expect. It shows you understand functional graphs, indegree-based pruning, and how to treat special two-cycles differently from longer cycles. The DP-on-trees variant is equally optimal but typically appears as a refinement once you recognize the underlying graph structure.
This approach involves detecting cycles in the graph created by the favorite relationships. Each employee can be represented as a node in a graph, and a directed edge from employee i to employee favorite[i]. The problem can then be broken down into finding the longest cycle and managing chain connections to nodes forming such cycles.
In the solution provided, we utilize Depth First Search (DFS) to identify cycles by keeping track of nodes already visited and recurrence depth. The key is recognizing cycles in this graph representation and thus calculating the maximum employees from these cycles. This code is a general template, emphasizing the calculation of cycle lengths.
Time Complexity: O(n) for traversing each node once. Space Complexity: O(n) for storage of visited states and stack sizes.
Another approach is to tackle this problem using dynamic programming. By considering the problem as one on a tree with nodes having specific dependencies (favorite person), we plant roots for our trees where the nodes represent employees and dependencies represent favorites.
The Java solution builds a tree representation using adjacency lists by converting the favorite relationships into a tree structure. Depth-First Search is applied to find the longest paths, while we track each node's depth in a dynamic programming table for efficiency and accuracy.
Java
JavaScript
Time Complexity: O(n), as we perform DFS rooted at each node once. Space Complexity: O(n) for the adjacency list and visited states.
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.
What is a "base cycle inward tree"? First, a base cycle tree is a directed graph with n nodes and n edges, and an inward tree means that in this directed graph, each node has exactly one outgoing edge. In this problem, each employee has exactly one favorite employee, so the constructed directed graph can be composed of multiple "base cycle inward trees".
For this problem, we can find the length of the maximum cycle in the graph. Here we only need to find the length of the largest cycle, because if there are multiple cycles, they are not connected to each other, which does not meet the problem requirements.
In addition, for the size of the cycle equal to 2, that is, there are two employees who like each other, then we can arrange these two employees together. If these two employees are each liked by other employees, then we only need to arrange the employees who like them next to them. If there are multiple such situations, we can arrange them all.
Therefore, the problem is actually equivalent to finding the length of the maximum cycle in the graph, and all cycles of length 2 plus their longest chain. The maximum of these two can be found. To find the longest chain to the cycle of length 2, we can use topological sorting.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array favorite.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Graph Cycle Detection and Maximum Matching | Time Complexity: O(n) for traversing each node once. Space Complexity: O(n) for storage of visited states and stack sizes. |
| Approach 2: Dynamic Programming on Trees | Time Complexity: O(n), as we perform DFS rooted at each node once. Space Complexity: O(n) for the adjacency list and visited states. |
| Maximum Cycle in Graph + Longest Chain | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Cycle Detection + Topological Sort | O(n) | O(n) | Best general solution. Efficiently handles cycles and chain extensions using indegree pruning. |
| Dynamic Programming on Trees | O(n) | O(n) | Useful when modeling incoming chains as trees and computing depths via DFS. |
Maximum Employees to Be Invited to a Meeting - Leetcode 2127 - Python • NeetCodeIO • 14,597 views views
Watch 9 more video solutions →Practice Maximum Employees to Be Invited to a Meeting with our built-in code editor and test cases.
Practice on FleetCode