Introduction

I encountered recently an interesting LeetCode challenge“Maximum Employees to Be Invited to a Meeting.” The statement of the problem is pretty straightforward: we have a round table, and each employee has exactly one “favorite” colleague they would prefer to sit next to. Our goal is to determine the maximum number of employees who can be invited while respecting the seating preferences(i.e. each employee seats next to his favourite colleague).

The constraints are pretty strict: the amount of employees is about 10^5, meaning that preferable asymptotic run time should be O(n) or O(n log(n)), but not O(n2).

Idea of the solution

Formulating the problem using the language of graph theory is essential, though not that straightforward. We are considering a directed graph where each vertex has exactly one outgoing edge. Since the graph is finite it can be viewed as a union of tailed loops: a set of components, each containing exactly one loop (circle) along with some incoming tails to the vertices of the loop:

The objective is to find a subset of vertices of maximum size such that for each included vertex the endpoint of its corresponding outgoing edge is also included in the subset and we can fit them on a table. Let’s try to describe the second condition in a bit more details.

We observe first that since each employee wants to sit next to their favourite colleague every possible arrangement must contain a loop.

Now, there are two completely different cases to consider:

  1. The loop has 3 or more people.
    In this case, the loop forms a self-contained group, and no additional employees can be invited outside of this loop(as one should go to the left and another one to the right occupying all the free spaces). The size of the loop itself determines the number of employees who can participate. Therefore, the solution must account for the largest such loop in the arrangement.
  2. The loop has exactly 2 people.
    This case is more interesting. If two employees mutually prefer each other, they can form the core of the arrangement. Around this pair, we can extend chains of other employees who ultimately “flow” into this pair. The total size of this group is the length of both chains plus the two members of the pair. And surprisingly in this case we can combine as many such two-vertex tailed loops as possible.

This means that the answer is the maximum of two numbers: the length of the largest loop with a length of at least three and the sum of the lengths of the two-vertex tailed loops.

An algorithm and Implementation

A naive implementation of the above idea works as follows. First, we recall that each “connected component” has exactly one loop. So, we loop over the vertices check that we haven’t visited them already and verify that there is an incoming edge. If these conditions are met we are “in a circle” and there are two cases: the vertex belongs to a loop of length two, or a loop strictly longer than two. In the first case, we compute the maximum length of the incoming tails, and in the second case, we try to find the total length of the loop.

Below is the C# implementation of this idea:

public class Solution {
    private HashSet<int> visited = new HashSet<int>();
    private Dictionary<int, HashSet<int>> inverse = new Dictionary<int, HashSet<int>>();

    public int MaximumInvitations(int[] favorite) 
    {
        var n = favorite.Length;

        var maxResultViaCircles = 0;
        var maxResultViaTails = 0;

        var pairs = new HashSet<(int, int)>();

        for (int i = 0; i < n; ++i)
        {
            var key = favorite[i];
            inverse.TryAdd(key, new HashSet<int>());
            inverse[key].Add(i);

            if( favorite[favorite[i]] == i && i < favorite[i])
            {
                pairs.Add((i, favorite[i]));
            }
        }

        var resultViaTailedLoops = ProcessTwoVertexLoops(pairs);

        for (int i = 0; i < n; ++i)
        {
            if (!visited.Contains(i) && inverse.ContainsKey(i))
            {
                maxResultViaCircles = Math.Max(maxResultViaCircles, FindLoopRadius(i, favorite)); 
            }
        }

        return Math.Max(resultViaTailedLoops, maxResultViaCircles);
    }

    public int ProcessTwoVertexLoops(HashSet<(int, int)> pairs)
    {
        var result = 0;
        foreach (var (start, end) in pairs)
        {
            visited.Add(start);
            visited.Add(end);
            
            result += FindMaxTail(start, end);
            result += FindMaxTail(end, start);
        }

        return result;
    }

    private int FindMaxTail(int start, int end)
    {
        var result = 0;
        var toVisit = new HashSet<int> { start };

        visited.Add(start);
        visited.Add(end);

        while (toVisit.Count > 0)
        {
            var newToVisit = new HashSet<int>();

            foreach (var candidate in toVisit)
            {
                visited.Add(candidate);
                if (inverse.ContainsKey(candidate))
                {
                    foreach (var newCandidate in inverse[candidate])
                    {
                        if (!visited.Contains(newCandidate))
                        {
                            newToVisit.Add(newCandidate);
                        }
                    }
                }
            }

            toVisit = newToVisit;
            ++result;
        }

        return result;
    }

    private int FindLoopRadius(int i, int[] favorite)
    {
        var current = i;
        var seen = new HashSet<int>();
        var cycleLength = 0;

        while (!seen.Contains(current) && !visited.Contains(current)) 
        {
            seen.Add(current);
            visited.Add(current);
            current = favorite[current];
        }

        if(seen.Contains(current)) 
        {
            var start = current;
            while (true) 
            {
                cycleLength++;
                current = favorite[current];
                if (current == start) break;
            }
        }

        return cycleLength;
    }
}

A bit dirty and might be refactored, but passes all the test cases in a reasonable time: