LeetCode Solutions Blog

Maximum Employees to Be Invited to a Meeting

Number: 2246

Difficulty: Hard

Paid? No

Problem Description

There are n employees numbered from 0 to n - 1 each having a favorite person (which is not themselves). A circular table is available that can seat any number of employees. An employee will attend the meeting only if they are seated next to their favorite person. Given an array favorite where favorite[i] is the favorite person of employee i, determine the maximum number of employees that can be invited such that the seating arrangement satisfies everyone’s condition.

Key Insights

The problem can be interpreted in terms of cycles in a directed graph where each node points to its favorite.
A simple cycle represents an arrangement where each person’s favorite is adjacent.
Special attention is required for 2-cycles (mutual favorites); additional chains (longest paths ending at the nodes of the 2-cycle) can be attached to maximize the answer.
The final answer is the maximum between the size of the largest simple cycle and the sum of the lengths contributed by all 2-cycles (each plus its attached chains).

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

We start by modeling the problem as a graph where each employee i has a directed edge to favorite[i]. In this graph, a cycle indicates a valid seating if arranged as a round table. However, the twist is that for a 2-cycle (i.e., employee A’s favorite is B and vice versa), it is possible to attach additional paths (chains) to each node of the 2-cycle. To achieve this, we:

Find the longest cycle in the graph that is not a 2-cycle or is a standalone cycle.
Identify all 2-cycles, then for each integral 2-cycle pair, use DFS/BFS on the reversed edges (excluding the partner in the 2-cycle) to compute the longest chain that can be attached.
The overall answer becomes the maximum between the size of the largest cycle and the sum over all 2-cycles of (2 + length(chain from one node) + length(chain from the other node)).

Key data structures include an adjacency list for reverse lookups and arrays for tracking visited nodes and chain lengths.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java with line-by-line comments:

# Python solution

def maximumInvitations(favorite):
    n = len(favorite)
    
    # Build reverse graph: for each employee, maintain a list of employees who mark them as favorite
    reverse_adj = [[] for _ in range(n)]
    for i, fav in enumerate(favorite):
        reverse_adj[fav].append(i)
    
    # Helper DFS function to get the longest chain starting from node, excluding blocked neighbor (to prevent cycles)
    def dfs(node, blocked, visited):
        best = 0
        for nei in reverse_adj[node]:
            if nei == blocked or visited[nei]:
                continue
            visited[nei] = True
            best = max(best, 1 + dfs(nei, blocked, visited))
            visited[nei] = False
        return best

    # Step 1: Detect the maximum cycle length (for cycles not forming 2-cycles)
    max_cycle = 0
    visited_cycle = [False] * n
    for i in range(n):
        if visited_cycle[i]:
            continue
        index = {}
        cur = i
        step = 0
        # Traverse until a cycle is detected or a visited node encountered
        while cur not in index and not visited_cycle[cur]:
            index[cur] = step
            step += 1
            cur = favorite[cur]
        # If a cycle is detected
        if cur in index:
            cycle_length = step - index[cur]
            max_cycle = max(max_cycle, cycle_length)
        # Mark all nodes in this traversal as visited for cycle detection
        for node in index:
            visited_cycle[node] = True

    # Step 2: Identify all 2-cycles and attach the longest chains to both nodes.
    pair_sum = 0
    used = [False] * n  # For marking nodes part of a 2-cycle pair (this is optional)

    for i in range(n):
        j = favorite[i]
        # Check for 2-cycle condition: ensure i < j to count once.
        if favorite[j] == i and i < j:
            # For each node in the pair, try to get the longest chain not coming from the 2-cycle partner.
            visited1 = [False] * n
            visited1[i] = True
            visited1[j] = True
            chain1 = dfs(i, j, visited1)
            
            visited2 = [False] * n
            visited2[i] = True
            visited2[j] = True
            chain2 = dfs(j, i, visited2)
            
            # Add the chains attached to both nodes (2 for the pair itself)
            pair_sum += 2 + chain1 + chain2

    # Final answer is maximum of longest cycle and sum from 2-cycle structure.
    return max(max_cycle, pair_sum)

# Example usage:
favorite = [3,0,1,4,1]
print(maximumInvitations(favorite))  # Expected output: 4