Maximum Employees to Be Invited to a Meeting — Solution
Maximum Employees to Be Invited to a Meeting solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Employees to Be Invited to a Meeting is a hard coding problem on depth-first search, graph and topological sort, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Depth-First Search, Graph, Topological Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A company is planning a meeting at a large round table that can seat any number of people. Its n employees are numbered 0 to n - 1, and employee i has exactly one favourite colleague, favorite[i], who is never i themself.
An employee attends only if they can sit directly next to their favourite colleague (on either side).
Return the maximum number of employees who can be invited.
Example 1
Input: favorite = [1,0,0,1,3]
Output: 5
Explanation: 0 and 1 favour each other. Seat them together with 2 beside 0 and the chain 4 → 3 beside 1: 2, 0, 1, 3, 4 around the table works for everyone.
Example 2
Input: favorite = [1,2,3,0,0]
Output: 4
Explanation: 0 → 1 → 2 → 3 → 0 must sit as a closed loop, which leaves no seat next to 0 for employee 4.
Example 3
Input: favorite = [1,2,0]
Output: 3
Constraints
n == favorite.length2 <= n <= 10^50 <= favorite[i] <= n - 1favorite[i] != i
Hints for Maximum Employees to Be Invited to a Meeting
Hint 1
Draw an edge from each employee to their favourite. Every component of this graph is one cycle with trees hanging into it.
Hint 2
A cycle of length 3 or more can only be seated on its own, as exactly that cycle. A pair of mutual favourites (a 2-cycle) is different: each side can extend with a chain of people leading into it.
Hint 3
So the answer is the larger of: the longest cycle (length ≥ 3), or the sum over all mutual pairs of 2 + the longest chain into each partner. Peel the trees off with a topological sort to get the chain lengths.
How to solve Maximum Employees to Be Invited to a Meeting
The favourite graph is functional, so each component is a cycle plus in-trees. A long cycle fills the table alone; mutual pairs, each with the longest chain leading into either partner, can all be laid side by side around the table.
Approach
- Count in-degrees and queue everyone nobody favours (in-degree 0).
- Pop
u, letv = favorite[u], setdepth[v] = max(depth[v], depth[u] + 1), decrementv's in-degree and queue it at 0. Whatever is never popped lies on a cycle. - Walk each remaining cycle once to get its length. For a 2-cycle
(a, b)add2 + depth[a] + depth[b]to a running pair total; for longer cycles track the maximum length. - Return the larger of the longest cycle and the pair total.
Why it works
In a cycle of length ≥ 3 each member's two neighbours are forced (its favourite and whoever favours it on the cycle), so the table holds exactly that cycle and nobody else. In a mutual pair both partners are already satisfied by each other, leaving their outer sides free for a chain leading in — but only one chain per side, the longest. Such open-ended segments can be concatenated around the table without conflict, so all pairs contribute together. The topological peel computes, for every cycle node, the longest chain of tree nodes ending at it.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Treating 2-cycles like long cycles (taking only the maximum) undercounts — pairs add up.
- Only one chain per partner of a pair can be seated, so use the deepest chain, not the whole tree.
- Chains into a long cycle are useless, since nobody on that cycle has a free side.
Reference solution
Python
from typing import List
from collections import deque
def maximumInvitations(favorite: List[int]) -> int:
n = len(favorite)
indeg = [0] * n
for f in favorite:
indeg[f] += 1
depth = [0] * n
q = deque(i for i in range(n) if indeg[i] == 0)
while q:
u = q.popleft()
v = favorite[u]
if depth[u] + 1 > depth[v]:
depth[v] = depth[u] + 1
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
longest_cycle = 0
pairs = 0
for i in range(n):
if indeg[i] == 0:
continue
length = 0
j = i
while indeg[j] != 0:
indeg[j] = 0
length += 1
j = favorite[j]
if length == 2:
pairs += 2 + depth[i] + depth[favorite[i]]
else:
longest_cycle = max(longest_cycle, length)
return max(longest_cycle, pairs)Java
public static int maximumInvitations(int[] favorite) {
int n = favorite.length;
int[] indeg = new int[n], depth = new int[n], queue = new int[n];
for (int f : favorite) indeg[f]++;
int head = 0, tail = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[tail++] = i;
while (head < tail) {
int u = queue[head++], v = favorite[u];
depth[v] = Math.max(depth[v], depth[u] + 1);
if (--indeg[v] == 0) queue[tail++] = v;
}
int longestCycle = 0, pairs = 0;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) continue;
int len = 0, j = i;
while (indeg[j] != 0) { indeg[j] = 0; len++; j = favorite[j]; }
if (len == 2) pairs += 2 + depth[i] + depth[favorite[i]];
else longestCycle = Math.max(longestCycle, len);
}
return Math.max(longestCycle, pairs);
}C++
int maximumInvitations(vector<int>& favorite) {
int n = favorite.size();
vector<int> indeg(n, 0), depth(n, 0), queue;
for (int f : favorite) indeg[f]++;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.push_back(i);
for (size_t h = 0; h < queue.size(); h++) {
int u = queue[h], v = favorite[u];
depth[v] = max(depth[v], depth[u] + 1);
if (--indeg[v] == 0) queue.push_back(v);
}
int longestCycle = 0, pairs = 0;
for (int i = 0; i < n; i++) {
if (indeg[i] == 0) continue;
int len = 0, j = i;
while (indeg[j] != 0) { indeg[j] = 0; len++; j = favorite[j]; }
if (len == 2) pairs += 2 + depth[i] + depth[favorite[i]];
else longestCycle = max(longestCycle, len);
}
return max(longestCycle, pairs);
}JavaScript
var maximumInvitations = function(favorite) {
var n = favorite.length;
var indeg = [], depth = [];
for (var i = 0; i < n; i++) { indeg.push(0); depth.push(0); }
for (var k = 0; k < n; k++) indeg[favorite[k]]++;
var queue = [];
for (var s = 0; s < n; s++) if (indeg[s] === 0) queue.push(s);
for (var h = 0; h < queue.length; h++) {
var u = queue[h], v = favorite[u];
if (depth[u] + 1 > depth[v]) depth[v] = depth[u] + 1;
if (--indeg[v] === 0) queue.push(v);
}
var longestCycle = 0, pairs = 0;
for (var a = 0; a < n; a++) {
if (indeg[a] === 0) continue;
var len = 0, j = a;
while (indeg[j] !== 0) { indeg[j] = 0; len++; j = favorite[j]; }
if (len === 2) pairs += 2 + depth[a] + depth[favorite[a]];
else if (len > longestCycle) longestCycle = len;
}
return Math.max(longestCycle, pairs);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure