LeetCode 2127 - Maximum Employees to Be Invited to a Meeting

This problem describes a group of employees sitting around a circular table. Every employee has exactly one favorite coworker, represented by the array favorite, where favorite[i] is the person employee i wants to sit next to.

leetcodehardarraydynamic-programmingdepth-first-searchgraph-theorytopological-sort

LeetCode Problem 2127

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Depth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem describes a group of employees sitting around a circular table. Every employee has exactly one favorite coworker, represented by the array favorite, where favorite[i] is the person employee i wants to sit next to.

An employee will attend the meeting only if they can sit directly adjacent to their favorite employee at the circular table. Since the table is circular, every person has exactly two neighbors.

The goal is to determine the maximum number of employees that can be invited while still satisfying everyone's adjacency requirement.

The input forms a directed graph:

  • Each employee is a node.
  • Each employee points to exactly one other employee, their favorite.

Because every node has exactly one outgoing edge, the graph consists of directed cycles with trees feeding into those cycles.

The constraints are important:

  • n can be as large as 100000
  • A brute-force seating search is impossible
  • We need an algorithm close to linear time

There are two key structural observations:

  1. Large directed cycles can form valid circular seating arrangements directly.
  2. Mutual favorite pairs, cycles of length 2, behave differently because chains can be attached to both sides of the pair.

Understanding these two cases is the core of the solution.

Several edge cases can easily break naive implementations:

  • A graph containing one large cycle
  • Multiple disconnected cycles
  • Two-node cycles with long incoming chains
  • Deep chains feeding into cycles
  • Employees not belonging to the optimal configuration

The problem guarantees:

  • No employee favorites themself
  • Every node has exactly one outgoing edge
  • The graph is always composed of cycles and incoming trees

Approaches

Brute Force Approach

A brute-force solution would attempt to generate subsets of employees and test all possible circular seatings.

For every subset:

  1. Generate all permutations
  2. Place employees around the table
  3. Check whether each employee sits next to their favorite

This works because it explicitly verifies every possible valid arrangement.

However, the complexity is catastrophic. For n = 100000, even enumerating subsets is impossible, let alone permutations.

The problem requires exploiting the graph structure instead of searching seat arrangements directly.

Key Insight

Since every employee points to exactly one favorite, the graph is a functional graph.

A functional graph consists of:

  • Directed cycles
  • Trees feeding into those cycles

There are only two configurations that can contribute to the optimal answer:

  1. A single cycle of length greater than 2
  2. Multiple mutual favorite pairs, cycles of length 2, each extended with the longest incoming chains

Why are cycles of length 2 special?

Suppose employees a and b favorite each other:

a <-> b

They can sit together, and additional chains can attach to either side:

chain -> a <-> b <- chain

This is not possible for larger cycles because every seat adjacent to the cycle members is already occupied.

Therefore:

  • For cycles of length >= 3, only the cycle itself counts
  • For cycles of length 2, we can add the longest incoming chain into each node

The final answer is:

max(
    largest_cycle_length,
    sum_of_all_extended_two_cycles
)

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Tries all seatings explicitly
Optimal O(n) O(n) Uses graph structure and topological pruning

Algorithm Walkthrough

Step 1: Build the indegree array

For every employee i:

favorite[i] -> target

Increment the indegree of target.

The indegree tells us how many employees point to each person.

We need this for topological pruning.

Step 2: Compute longest incoming chains

We perform a topological sort using Kahn's algorithm.

Employees with indegree 0 cannot belong to a cycle, so they must be part of a chain leading into a cycle.

We process these nodes layer by layer.

For each employee:

next_employee = favorite[current]

We update:

longest_chain[next_employee] =
    max(longest_chain[next_employee],
        longest_chain[current] + 1)

This computes the maximum chain length entering every node.

Step 3: Remove non-cycle nodes

As nodes are processed:

  • Reduce indegrees
  • Push newly zero-indegree nodes into the queue

At the end:

  • Nodes with indegree > 0 belong to cycles
  • Nodes with indegree 0 were pruned away

This cleanly isolates all cycles.

Step 4: Traverse cycles

Now iterate through all remaining cycle nodes.

For each unvisited cycle:

  1. Walk through the cycle
  2. Count its size

There are two cases.

Case A: Cycle length is 2

Suppose:

a <-> b

Then contribution is:

longest_chain[a] + longest_chain[b]

because both sides can accept incoming chains.

Add this contribution to the total two-cycle answer.

Case B: Cycle length >= 3

Only the cycle itself can participate.

Update:

largest_cycle = max(largest_cycle, cycle_length)

Step 5: Return the final answer

The optimal arrangement is either:

  • One large cycle
  • The sum of all extended two-cycles

Return:

max(largest_cycle, two_cycle_total)

Why it works

Every node belongs either to a cycle or to a tree leading into a cycle.

Cycles of length >= 3 already consume all adjacency positions, so no extra chains can attach.

Cycles of length 2 leave one free side on each employee, allowing the longest incoming chain on each side to be added.

The algorithm correctly separates these two structures and computes the best possible contribution from each.

Since every node is processed exactly once during pruning and once during cycle detection, the result is both correct and efficient.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)

        indegree = [0] * n

        for person in favorite:
            indegree[person] += 1

        longest_chain = [1] * n

        queue = deque()

        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)

        while queue:
            current = queue.popleft()

            next_person = favorite[current]

            longest_chain[next_person] = max(
                longest_chain[next_person],
                longest_chain[current] + 1
            )

            indegree[next_person] -= 1

            if indegree[next_person] == 0:
                queue.append(next_person)

        visited = [False] * n

        largest_cycle = 0
        two_cycle_total = 0

        for i in range(n):
            if indegree[i] > 0 and not visited[i]:
                cycle_length = 0
                current = i

                while not visited[current]:
                    visited[current] = True
                    current = favorite[current]
                    cycle_length += 1

                if cycle_length == 2:
                    a = i
                    b = favorite[i]

                    two_cycle_total += (
                        longest_chain[a] + longest_chain[b]
                    )
                else:
                    largest_cycle = max(
                        largest_cycle,
                        cycle_length
                    )

        return max(largest_cycle, two_cycle_total)

The implementation begins by computing indegrees for all employees. Since each employee points to exactly one favorite, this is straightforward.

The longest_chain array stores the maximum chain length ending at each node. Every node initially contributes length 1, representing itself.

Kahn's algorithm removes all non-cycle nodes. While removing nodes, the algorithm propagates chain lengths forward through the graph.

After pruning finishes, only cycle nodes remain with positive indegree.

The second phase traverses the remaining cycles. The algorithm distinguishes between:

  • Two-node cycles
  • Larger cycles

For two-node cycles, the longest chains entering both nodes are added. For larger cycles, only the cycle length itself contributes.

Finally, the algorithm returns the larger of:

  • The largest cycle
  • The total contribution from all extended two-cycles

Go Solution

package main

func maximumInvitations(favorite []int) int {
	n := len(favorite)

	indegree := make([]int, n)

	for _, person := range favorite {
		indegree[person]++
	}

	longestChain := make([]int, n)

	for i := 0; i < n; i++ {
		longestChain[i] = 1
	}

	queue := make([]int, 0)

	for i := 0; i < n; i++ {
		if indegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	head := 0

	for head < len(queue) {
		current := queue[head]
		head++

		nextPerson := favorite[current]

		if longestChain[current]+1 > longestChain[nextPerson] {
			longestChain[nextPerson] =
				longestChain[current] + 1
		}

		indegree[nextPerson]--

		if indegree[nextPerson] == 0 {
			queue = append(queue, nextPerson)
		}
	}

	visited := make([]bool, n)

	largestCycle := 0
	twoCycleTotal := 0

	for i := 0; i < n; i++ {
		if indegree[i] > 0 && !visited[i] {

			cycleLength := 0
			current := i

			for !visited[current] {
				visited[current] = true
				current = favorite[current]
				cycleLength++
			}

			if cycleLength == 2 {
				a := i
				b := favorite[i]

				twoCycleTotal +=
					longestChain[a] + longestChain[b]
			} else {
				if cycleLength > largestCycle {
					largestCycle = cycleLength
				}
			}
		}
	}

	if largestCycle > twoCycleTotal {
		return largestCycle
	}

	return twoCycleTotal
}

The Go implementation follows the same logic as the Python version.

Instead of using a deque, the queue is implemented using a slice with a moving head index. This avoids costly front removals.

Go slices are dynamically sized, making them suitable for queue simulation.

No integer overflow concerns exist because the maximum answer is at most 100000.

Worked Examples

Example 1

favorite = [2,2,1,2]

Step 1: Build indegrees

Employee Favorite Indegree
0 2 0
1 2 1
2 1 3
3 2 0

Initial indegrees:

[0,1,3,0]

Step 2: Topological pruning

Initial queue:

[0,3]

Initial longest chains:

[1,1,1,1]

Process employee 0:

0 -> 2

Update:

longest_chain[2] = 2

Indegree of 2 becomes 2.

Process employee 3:

3 -> 2

Update:

longest_chain[2] = 2

Indegree of 2 becomes 1.

Queue becomes empty.

Remaining cycle:

1 <-> 2

Step 3: Handle two-cycle

Chain into 1:

1

Chain into 2:

2

Contribution:

1 + 2 = 3

Answer:

3

Example 2

favorite = [1,2,0]

Graph:

0 -> 1 -> 2 -> 0

This forms a cycle of length 3.

No chains exist.

Largest cycle:

3

Two-cycle contribution:

0

Answer:

3

Example 3

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

Graph:

0 -> 3
1 -> 0
2 -> 1
3 -> 4
4 -> 1

Cycle:

0 -> 3 -> 4 -> 1 -> 0

Cycle length:

4

Employee 2 points into the cycle but cannot be added because all adjacency positions are already occupied.

Answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node and edge is processed a constant number of times
Space O(n) Arrays, queue, and visited tracking all require linear space

Each employee is added to the queue at most once and visited during cycle detection at most once. Since the graph contains exactly n edges, all operations remain linear.

Test Cases

from typing import List

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        from collections import deque

        n = len(favorite)

        indegree = [0] * n

        for person in favorite:
            indegree[person] += 1

        longest_chain = [1] * n

        queue = deque()

        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)

        while queue:
            current = queue.popleft()

            next_person = favorite[current]

            longest_chain[next_person] = max(
                longest_chain[next_person],
                longest_chain[current] + 1
            )

            indegree[next_person] -= 1

            if indegree[next_person] == 0:
                queue.append(next_person)

        visited = [False] * n

        largest_cycle = 0
        two_cycle_total = 0

        for i in range(n):
            if indegree[i] > 0 and not visited[i]:
                cycle_length = 0
                current = i

                while not visited[current]:
                    visited[current] = True
                    current = favorite[current]
                    cycle_length += 1

                if cycle_length == 2:
                    a = i
                    b = favorite[i]

                    two_cycle_total += (
                        longest_chain[a] + longest_chain[b]
                    )
                else:
                    largest_cycle = max(
                        largest_cycle,
                        cycle_length
                    )

        return max(largest_cycle, two_cycle_total)

solution = Solution()

assert solution.maximumInvitations([2,2,1,2]) == 3  # example 1
assert solution.maximumInvitations([1,2,0]) == 3  # simple 3-cycle
assert solution.maximumInvitations([3,0,1,4,1]) == 4  # example 3

assert solution.maximumInvitations([1,0]) == 2  # smallest possible 2-cycle

assert solution.maximumInvitations([1,0,1]) == 3  # chain into 2-cycle

assert solution.maximumInvitations([1,2,3,0]) == 4  # single 4-cycle

assert solution.maximumInvitations([1,0,3,2]) == 4  # two disjoint 2-cycles

assert solution.maximumInvitations([2,2,1,5,5,4]) == 5  # multiple components

assert solution.maximumInvitations([1,2,0,2]) == 3  # extra node into large cycle

assert solution.maximumInvitations([1,0,0,0]) == 2  # only one chain can attach

assert solution.maximumInvitations([1,0,3,2,0,2]) == 6  # extended two-cycles

assert solution.maximumInvitations([1,2,3,4,0]) == 5  # large single cycle

Test Summary

Test Why
[2,2,1,2] Verifies two-cycle with chains
[1,2,0] Verifies simple cycle
[3,0,1,4,1] Verifies larger cycle handling
[1,0] Smallest valid input
[1,0,1] Chain entering two-cycle
[1,2,3,0] Large cycle only
[1,0,3,2] Multiple two-cycles
[2,2,1,5,5,4] Multiple disconnected components
[1,2,0,2] Chain into non-extendable cycle
[1,0,0,0] Competing chains into same node
[1,0,3,2,0,2] Multiple extendable pairs
[1,2,3,4,0] Entire graph is one cycle

Edge Cases

Two-node cycles with multiple incoming chains

A common bug is incorrectly attaching multiple chains to the same node in a two-cycle.

Consider:

favorite = [1,0,0,0]

Employees 2 and 3 both point to employee 0.

Only one chain can be attached because employee 0 has only one free adjacent seat outside the mutual pair.

The implementation correctly keeps only the longest incoming chain using:

max(existing, new_chain)

Large cycles cannot accept extra chains

Another common mistake is trying to attach chains to cycles longer than 2.

For example:

0 -> 1 -> 2 -> 0
3 -> 1

Employee 3 cannot be added because every cycle member already uses both neighboring seats inside the cycle.

The implementation handles this by counting only the cycle length for cycles of size >= 3.

Multiple disconnected components

The graph may contain several independent components.

Example:

[1,0,3,2]

This contains two separate two-cycles.

A buggy implementation might only process one connected component.

The solution iterates through all nodes and processes every remaining cycle independently, ensuring all valid contributions are included.