Maximum Employees to Be Invited to a Meeting

hard graph topological sort functional graph

Problem

Each employee i has exactly one favorite colleague favorite[i] and will only attend a meeting if seated directly next to that favorite. The meeting uses a single round table, so each invited person needs their favorite as one of their two neighbors. Return the maximum number of employees that can be invited at once.

Inputfavorite = [2, 2, 1, 2]

Output3

Persons 1 and 2 are mutual favorites (a 2-cycle). Seat them next to each other, then person 0 or 3 (who favor 2) on the outside: 0 → 2 → 1 gives three people, the most possible.

favorite (comma-separated indices)

def maximum_invitations(favorite):
    n = len(favorite)
    indeg = [0] * n
    for f in favorite:
        indeg[f] += 1
    depth = [1] * n
    q = [i for i in range(n) if indeg[i] == 0]
    seen = [False] * n
    while q:
        u = q.pop()
        seen[u] = True
        v = favorite[u]
        depth[v] = max(depth[v], depth[u] + 1)
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)
    max_cycle, two_sum = 0, 0
    for i in range(n):
        if seen[i]:
            continue
        nodes, k = [], i
        while not seen[k]:
            seen[k] = True
            nodes.append(k)
            k = favorite[k]
        if len(nodes) == 2:
            two_sum += depth[nodes[0]] + depth[nodes[1]]
        else:
            max_cycle = max(max_cycle, len(nodes))
    return max(max_cycle, two_sum)

function maximumInvitations(favorite) {
  const n = favorite.length;
  const indeg = new Array(n).fill(0);
  for (const f of favorite) indeg[f]++;
  const depth = new Array(n).fill(1);
  const q = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const seen = new Array(n).fill(false);
  while (q.length) {
    const u = q.pop();
    seen[u] = true;
    const v = favorite[u];
    depth[v] = Math.max(depth[v], depth[u] + 1);
    if (--indeg[v] === 0) q.push(v);
  }
  let maxCycle = 0, twoSum = 0;
  for (let i = 0; i < n; i++) {
    if (seen[i]) continue;
    const nodes = [];
    let k = i;
    while (!seen[k]) { seen[k] = true; nodes.push(k); k = favorite[k]; }
    if (nodes.length === 2) twoSum += depth[nodes[0]] + depth[nodes[1]];
    else maxCycle = Math.max(maxCycle, nodes.length);
  }
  return Math.max(maxCycle, twoSum);
}

class Solution {
    public int maximumInvitations(int[] favorite) {
        int n = favorite.length;
        int[] indeg = new int[n];
        for (int f : favorite) indeg[f]++;
        int[] depth = new int[n];
        Arrays.fill(depth, 1);
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
        boolean[] seen = new boolean[n];
        while (!q.isEmpty()) {
            int u = q.pop();
            seen[u] = true;
            int v = favorite[u];
            depth[v] = Math.max(depth[v], depth[u] + 1);
            if (--indeg[v] == 0) q.push(v);
        }
        int maxCycle = 0, twoSum = 0;
        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;
            int len = 0, k = i, a = i, b = i;
            while (!seen[k]) { seen[k] = true; a = b; b = k; k = favorite[k]; len++; }
            if (len == 2) twoSum += depth[a] + depth[b];
            else maxCycle = Math.max(maxCycle, len);
        }
        return Math.max(maxCycle, twoSum);
    }
}

int maximumInvitations(vector<int>& favorite) {
    int n = favorite.size();
    vector<int> indeg(n, 0), depth(n, 1);
    for (int f : favorite) indeg[f]++;
    vector<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push_back(i);
    vector<bool> seen(n, false);
    while (!q.empty()) {
        int u = q.back(); q.pop_back();
        seen[u] = true;
        int v = favorite[u];
        depth[v] = max(depth[v], depth[u] + 1);
        if (--indeg[v] == 0) q.push_back(v);
    }
    int maxCycle = 0, twoSum = 0;
    for (int i = 0; i < n; i++) {
        if (seen[i]) continue;
        int len = 0, k = i, a = i, b = i;
        while (!seen[k]) { seen[k] = true; a = b; b = k; k = favorite[k]; len++; }
        if (len == 2) twoSum += depth[a] + depth[b];
        else maxCycle = max(maxCycle, len);
    }
    return max(maxCycle, twoSum);
}

Explanation

Draw an arrow from every person to their favorite. Since each person has exactly one favorite, this is a functional graph: every node has out-degree 1, so each connected piece is a single cycle with trees hanging off it.

Around a round table, a valid seating is just a cycle of the graph: everyone in the cycle has their favorite as a neighbor. So one candidate answer is the length of the longest cycle in the graph.

There is a second, sneakier candidate. A 2-cycle is a mutual pair a → b and b → a. Two such people are happy side by side, and crucially we can extend the line outward: anyone whose favorite is a can sit on a's free side, then anyone whose favorite is that person, and so on — a whole chain feeding into a, and likewise into b. Because every 2-cycle plus its tails forms an independent straight segment, we can seat all of them at the same table at once and simply add their sizes together.

To measure those tails we peel the graph like a topological sort. Count each node's in-degree, then repeatedly remove in-degree-0 nodes (people nobody favors). As we remove a node u pointing to v, we record depth[v] = max(depth[v], depth[u] + 1), the longest chain of tail-people ending at v. Whatever survives the peeling is exactly the cycle nodes.

Finally we trace each remaining cycle. Length-2 cycles contribute depth[a] + depth[b] (each side already includes its incoming chain) and we sum these across all 2-cycles. Longer cycles compete for the single largest-cycle slot. The answer is the larger of those two totals.

Example: favorite = [2, 2, 1, 2]. Persons 1 and 2 form the only 2-cycle; persons 0 and 3 are tails feeding into 2, so depth[2] = 2 and depth[1] = 1, giving 2 + 1 = 3. There is no cycle of length 3 or more, so the answer is 3.

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