2127. Maximum Employees to Be Invited to a Meeting - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

A company is organizing a meeting around a large circular table and has a list of n employees (labeled from 0 to n-1) to potentially invite. Each employee has one favorite person in the company. An employee will attend the meeting only if they can sit next to their favorite person at the table. (Note: No one has themselves as their own favorite, i.e., favorite[i] != i for all i.)

You are given a 0-indexed integer array favorite of length n, where favorite[i] is the index of the favorite person of employee i. Your task is to determine the maximum number of employees that can be invited such that all invited employees can be seated around the table satisfying the condition (each invited person sits next to their favorite person).

Examples:

Example 1:
Input: favorite = [2, 2, 1, 2]
Output: 3
Explanation: In this case, employees 0, 1, and 2 can be invited. One possible seating arrangement is a circle of these three employees. For instance, seat them in the order [0, 2, 1] around the table:
- Employee 0 sits next to employee 2 (and employee 2 is 0's favorite).
- Employee 1 sits next to employee 2 (and employee 2 is 1's favorite).
- Employee 2 sits next to employee 1 (and employee 1 is 2's favorite).
  All three are happy. Employee 3 cannot be invited at the same time because three different people (0, 1, and 3) all have 2 as their favorite, but employee 2 only has two adjacent seats. This means at least one of them would not be able to sit next to 2, violating the condition. The maximum number of attendees is 3.
Example 2:
Input: favorite = [1, 2, 0]
Output: 3
Explanation: Here every employee likes someone in a cycle: 0 likes 1, 1 likes 2, and 2 likes 0. They form a cycle of 3. We can invite all three and sit them as [0, 1, 2] around the table.
- Employee 0 sits next to 1 (favorite of 0 is 1).
- Employee 1 sits next to 2 (favorite of 1 is 2).
- Employee 2 sits next to 0 (favorite of 2 is 0).
  This seating satisfies everyone, so the answer is 3 (invite all employees).
Example 3:
Input: favorite = [3, 0, 1, 4, 1]
Output: 4
Explanation: One optimal set of invitees is employees 0, 1, 3, 4. These four can sit in a circle satisfying everyone’s condition. One possible seating order is [0, 3, 4, 1]:
- Employee 0 sits next to 3 (favorite of 0 is 3).
- Employee 3 sits next to 4 (favorite of 3 is 4).
- Employee 4 sits next to 1 (favorite of 4 is 1).
- Employee 1 sits next to 0 (favorite of 1 is 0).
  Every invited person has their favorite neighbor. Employee 2 is left out because their favorite is 1, but employee 1’s two adjacent seats are already occupied by 0 and 4 in this arrangement. So 2 cannot sit next to 1 without breaking someone else’s requirement. Thus, the maximum is 4.

Constraints:

n == favorite.length
2 <= n <= 100,000
0 <= favorite[i] < n (each favorite index is a valid employee)
favorite[i] != i (no one is their own favorite)

Hints

Hint 1: Try modeling the problem as a directed graph. Each employee can be thought of as a node, and there is a directed edge from node i to node favorite[i]. What properties does this graph have given that each node has exactly one outgoing edge?
Hint 2: In such a graph (where each node has one outgoing edge), every node eventually leads into a cycle. Think about the different cycle structures that can occur. For example, you might have a cycle of length 3 (A → B → C → A), a cycle of length 2 (A → B → A, meaning A and B are each other’s favorites), etc., with possibly some "chain" of nodes feeding into these cycles.
Hint 3: Consider two scenarios for seating:
1. Everyone sits in one cycle (circle) – If a group of employees form a cycle where each person likes the next, you can seat them all around the table in that cycle order. What is the largest cycle you can find?
2. Special case: cycle of length 2 (mutual favorites) – If two employees like each other, they can sit next to each other. Other employees who like one of them could sit on their other side. How would you maximize invitations in this scenario?
Hint 4: If multiple people like the same person, remember that person only has two sides at the table. This means only up to two of their admirers can sit next to them (one on each side). This hint is especially relevant for the case where several employees have the same favorite.
Hint 5: Think about using cycle detection (to find cycles in the graph) and topological sort or depth-first search (to handle the chains of employees leading into cycles). Combining these insights will lead to an optimal solution.

Approach Explanation

We will discuss two approaches: a brute-force approach (to illustrate the problem’s complexity) and an optimized graph-based approach that leverages cycle detection and chain lengths.

Approach 1: Brute Force (Permutation/Backtracking)

Idea: In a brute-force approach, one might try to generate all possible subsets or permutations of employees and check if there's a seating arrangement that satisfies the conditions. This could involve placing employees around a table in every possible order and verifying the condition for each arrangement.

Why it's difficult: The number of ways to seat n people around a table is extremely large (factorial growth). Even for moderate n, this is infeasible. For example, with n = 10, there are 10! = 3,628,800 possible seatings, and with larger n the number skyrockets. We need a more clever way to reason about the problem rather than brute-forcing seat arrangements.

Brute-force attempt (conceptual steps):

Generate seating arrangements: Try all permutations of employees (or all subsets of a certain size). For each potential set of invitees, arrange them in a circle in every possible order.
Check seating condition: For each arrangement, verify that every employee in that arrangement sits next to their favorite person (their favorite must appear either immediately to their left or right in the circle).
Track the maximum valid arrangement size: Among all arrangements that satisfy the condition, record the largest number of people.

Why it fails for large n: This approach is computationally infeasible due to exponential (factorial) complexity. With n up to 100,000, we cannot even enumerate all arrangements for small fractions of that number. We need to use the structure of the problem (the favorite relationships) to our advantage.

Approach 2: Using Graph Cycles and Chains (Optimal Solution)

Idea: Use the directed graph model and analyze its structure. Since each employee points to exactly one favorite, each connected component of this graph consists of one cycle with possibly several incoming chains feeding into that cycle. There are two key components to consider:

Cycles: A cycle represents a group of employees who can all sit in a circle together (each one’s favorite is the next person in the cycle).
Chains (or "in-arborescences"): A chain is a sequence of people that leads into a cycle. For example, X → Y → Z → ... → A, where A is on a cycle. People on the chain are only satisfied if they eventually sit next to the person they point to on the chain (Y next to A in this example), so they essentially need to be attached to the cycle.

Approach Breakdown:

Identify all cycles in the graph: Traverse the graph to find cycles. A cycle occurs when following the favorite pointers from some employee eventually loops back to an employee seen before. We can use cycle detection (via depth-first search or iterative traversal with visited markers) to find:
- The length of each cycle.
- Particularly note the longest cycle length, because a cycle of length L means L people can sit together satisfying each other (this is one candidate for the answer).
Handle cycle of length 2 (mutual favorites) separately: A cycle of length 2 is a special case: it means employee i likes j and j likes i. If i and j are mutual favorites, they can definitely sit next to each other. But unlike larger cycles, we can potentially invite other people around them by attaching those who like i or j to their other side. Specifically:
- If i and j like each other, seat i and j next to each other. Now i has one free neighboring seat (on the other side of the table from j), and j has one free neighboring seat (on the other side from i).
- We can attach at most one person to each of those free seats such that those attached people are satisfied. Who would we attach? Ideally, the people who most want to sit next to i or j (i.e., those who have i or j as their favorite). In fact, we can attach an entire chain of people into that seat as long as each person in the chain is sitting next to their favorite (which forms a linear chain ending at i or j).
- For each mutual-favorite pair, determine the longest chain of people ending at i and the longest chain ending at j (these chains represent people who ultimately want to sit next to i or j). We will attach the longest possible chain to i and to j to maximize how many can join.
- The total number of people we can include from this structure is: chain_length_into_i + chain_length_into_j + 2 (for i and j themselves). However, it’s easier to count it as chain_length_into_i (including i) plus chain_length_into_j (including j), since each chain length count can include the pair member itself.
Calculate chain lengths for all employees (to assist with step 2): We need to find, for each employee, how long a chain can be that ends in that employee. This can be done by analyzing the graph of reverse edges (who likes a given person). Specifically:
- Find all employees who no one has as a favorite (these are "leaves" with no incoming edges in the graph). These people cannot satisfy anyone else’s requirement if they’re invited, so if we’re looking at maximizing attendance, such individuals would only come if they themselves are satisfied by sitting next to their favorite. We treat them as starting points of chains that lead inward.
- Perform a topological-like traversal: remove those leaves from consideration (as invitees in large groups) and mark their favorite as having one less incoming edge (one less person who needs them). Continue this process iteratively: this effectively peels off the outermost people who can’t be part of a large cycle arrangement and computes how deep each chain is.
- As we remove a person X (with no one needing to sit next to X), we can increase the chain length count of X’s favorite (favorite[X]). Essentially, if X can sit next to favorite[X], we count X as a tail that can be attached. If X had a chain behind them of length L, then attaching X (and that chain) to favorite[X] yields a chain of length L+1 ending at favorite[X]. We keep track of the longest chain ending at each node during this process.
- After processing all possible leaves, the remaining people (not removed) are those that are in cycles. By then, for each person still in a cycle (especially those in 2-cycles), we will have computed the length of the longest chain that can feed into them.
Compare two possible invite counts:
- Option A: The length of the largest cycle found (this corresponds to inviting an entire cycle of that size).
- Option B: The sum of contributions from all mutual-favorite pairs with their attached chains. This means summing, for every pair of mutual favorites (i, j), the number of people that can be invited in that structure (which is the length of the longest chain ending at i plus the length of the longest chain ending at j). We sum across all such disjoint pairs because different mutual-favorite pairs involve different sets of people, and those pairs’ groups can all be seated around the table together. (In a seating, each pair+chains group will occupy a segment of the table, and we can arrange those segments in a loop since the pair groups don’t conflict with each other.)
- The answer is the maximum of these two values. We take the better of either taking one big cycle or combining all pair+chain structures.

Why this works: In a directed graph where each node has one outgoing edge (sometimes called a functional graph), every component is either:

One cycle by itself (possibly with trees feeding into it).
Or a cycle of length 2 (mutual favorites) with trees feeding into the two cycle nodes.

Cycles of length ≥ 3 are disjoint from each other in terms of invitees (you can only seat one cycle fully, because two separate cycles cannot be merged without someone losing their favorite neighbor). So the best you can do with large cycles is pick the largest one. However, 2-cycles are special: they can accept additional people on their sides, and multiple 2-cycle structures can be seated together by connecting their chains appropriately. That’s why we accumulate all 2-cycle structures together.

Step-by-step for Approach 2 (summary):

Build the directed graph from the favorite list.
Find all cycles: Use a DFS or iterative detection to find cycle lengths (especially track the maximum cycle length).
Find all 2-cycles (mutual favorites): These are easy to check: find all pairs (i, j) such that favorite[i] = j and favorite[j] = i. Mark these pairs for special handling.
Compute longest incoming chain for each node: Use a reverse graph or indegree count to perform a topological sort (Kahn’s algorithm):
- Initialize an array indegree for each node (how many people point to this node as favorite).
- Use a queue to remove nodes with indegree = 0 iteratively. Maintain an array dist (distance or chain length) where dist[x] is the length of the longest chain that ends at x (including x itself).
- For each removed node u (with no one needing u as favorite), update dist[favorite[u]] = max(dist[favorite[u]], dist[u] + 1) to extend the chain to u’s favorite, and decrement the indegree of favorite[u]. If indegree[favorite[u]] becomes 0, add that to the queue.
Calculate total for 2-cycles: For each mutual favorite pair (i, j), take the chain lengths computed for i and for j and add them together. (Make sure to count each pair only once; often one ensures i < j to avoid double counting the same pair in reverse.)
Finally, compare the sum of all 2-cycle structures vs. the largest cycle length found, and return the larger as the result.

By breaking the problem into these parts, we ensure we count the maximum possible invitees correctly.

Code Implementation

Below is the implementation of the optimal approach (Approach 2) in both Python and Java. The code follows the strategy described: it finds cycles and uses a topological sort to compute chain lengths, then computes the answer as discussed.

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

How the code works: Both implementations:

Find cycles by iterating through each person and marking visited. When a previously seen person is encountered during traversal, a cycle is found.
Use an indegree array and queue to compute how long a chain can extend into each person (this effectively finds longest paths in the acyclic "fan-in" trees).
Identify mutual favorite pairs and sum up their chain lengths.
Finally, take the maximum of the two scenarios.

Complexity Analysis

Time Complexity: The optimized approach runs in linear time relative to the number of employees:
- Finding cycles with DFS/graph traversal takes O(n) time. Each employee is visited at most once in the cycle-detection phase.
- Computing indegrees is O(n). The topological sort (peeling off leaves) also processes each person at most once, so O(n).
- Summing up pair contributions is O(n) (just a loop through the array).
- Overall, the time complexity is O(n) for the optimal approach. This is efficient enough for n up to 100,000. In contrast, a brute-force search of arrangements would be exponential (essentially O(n!) for checking all seatings), which is completely impractical.
Space Complexity:
- Storing the favorite list itself takes O(n).
- Additional arrays like visited, indegree, dist, and some auxiliary data structures (stack/queue) also take O(n) space.
- The space complexity is O(n). There may be some additional overhead for recursion or the path list in cycle detection, but that is also bounded by O(n) in the worst case.

The solution efficiently uses linear time and space, making it scalable to large inputs.

Common Mistakes and Edge Cases

Common Mistakes:

Assuming one strategy fits all: Some might assume that the answer is always the size of the largest cycle or always the sum of certain structures. In reality, you must consider both the largest cycle and the special handling of 2-cycles + chains. Forgetting one of these components will fail on certain test cases.
Combining multiple cycles incorrectly: Trying to invite two separate large cycles (of length > 2) at the same meeting will fail because you can't seat two disjoint cycles together without someone losing their favorite neighbor. The solution should not sum lengths of multiple disjoint cycles (except 2-cycles which can be combined via chains as discussed). The correct approach is to take the single largest cycle if that yields the max.
Double counting in pair chains: When summing up contributions from mutual favorite pairs, be careful not to count a pair twice. For example, if (i, j) is a mutual favorite pair, once you add the contribution for i and j, ensure you don’t add it again when you encounter j in the loop. Using a condition like i < j or a boolean flag can prevent double counting.
Misinterpreting the seating condition: Each employee only needs one favorite neighbor, not both. A common confusion is to think each person must sit directly between two favorites, but the problem clearly states "they will attend only if they can sit next to their favorite person" (singular). This means having their favorite on one side is enough; the other side neighbor can be anyone. Solutions that mistakenly enforce a stronger condition (like both neighbors must be favorites) will underestimate the number of invitees.

Edge Cases to Consider:

Small n (n=2 or n=3): Minimum case with 2 employees will always be mutual favorites due to constraints (person 0 must favor 1 and person 1 favors 0), so answer is 2. For n=3, you might have a cycle of 3 or a cycle of 2 with an extra person. Make sure the logic handles these correctly.
All employees in one cycle: e.g., favorite = [1, 2, 3, ..., 0] forming a big loop. The answer should be n (everyone can be invited).
Multiple mutual pairs without other connections: e.g., favorite = [1,0, 3,2, 5,4] (three disjoint 2-cycles). The answer here would be 6 because all three pairs can be invited (they can be arranged around the table in an alternating fashion, each pair sitting together).
One employee favored by many: e.g., one person is the favorite of everyone else. Only two of those "fans" can sit next to that person at once (one on each side). The algorithm’s chain calculation and indegree logic handle this by allowing only the two longest chains to attach (essentially two fans in this case). Check that your solution doesn’t try to invite all of them erroneously.
Chains of different lengths: Ensure that when computing chain lengths, you always take the longest chain into account for each side of a pair. If two or more people want to sit next to the same person, only one of them (the one at the end of the longest incoming chain) can actually occupy that seat in the optimal arrangement.
No mutual favorites at all: If no pair of employees like each other, then the answer must come from a single cycle (or possibly 1 if something went wrong with preferences, but constraints guarantee each component has a cycle). The solution should correctly fall back to the longest cycle in that case.
No cycles other than 2-cycles: It’s possible that the graph is made up only of 2-cycles (pairs) and chains feeding them, with no larger cycle. In this case, the answer will come from summing all pair structures. Make sure that logic is implemented (summing all pairs, not just picking one pair).

By carefully considering these cases, you can avoid pitfalls that lead to incorrect results.

This problem involves graph cycles and longest paths in a constrained scenario. Here are some related problems and variations that can deepen understanding:

Longest Cycle in a Graph (LeetCode 2360): This is a simpler problem focusing on finding the longest cycle in a directed graph. In that problem, each node can have at most one outgoing edge. It’s similar to the cycle detection part of this problem (but without the extra complexity of handling 2-cycles with chains). Solving it uses a similar DFS or graph traversal approach to detect cycles.
Course Schedule (LeetCode 207) and Course Schedule II (LeetCode 210): These problems involve detecting cycles in directed graphs and using topological sort (Kahn’s algorithm) to order nodes. While the context is different (prerequisite courses), the technique of removing nodes with indegree 0 and processing a graph is analogous to how we removed “leaf” employees in the chain computation.
Couples Holding Hands (LeetCode 765): This is a problem about seating couples next to each other with minimum swaps. While the problem and solution are quite different in details (it involves greedy pairing and swap operations), it also deals with an optimal arrangement around seats (in this case, a row of seats) to satisfy pairing constraints. It shows another scenario of pairing people optimally, which is conceptually related to satisfying neighbor preferences.
Detecting a Cycle in a Linked List: This classic problem (finding a loop in a linked list) relates because a linked list with a cycle is essentially a special case of a directed graph where each node has one outgoing edge (the next pointer). The cycle detection techniques (Floyd’s Tortoise and Hare algorithm or using a visited set) are relevant to detecting cycles in the "favorite" graph as well.
General graph cycle detection and longest path problems: In a general directed graph, finding the longest cycle or longest path is much harder (in fact, longest path is NP-hard). But this problem’s special structure (each node has exactly one outgoing edge) turns it into something manageable with linear time algorithms. It’s a good example of how imposing structure on a graph (like the functional graph structure here) can simplify an otherwise difficult problem.