Maximum Employees to Be Invited to a Meeting

Hard
1534.

Maximum Employees to Be Invited to a Meeting

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.

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.length
  • 2 <= n <= 10^5
  • 0 <= favorite[i] <= n - 1
  • favorite[i] != i
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} favorite
 * @return {number}
 */
var maximumInvitations = function(favorite) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 2 <= n <= 10^5
  • 0 <= favorite[i] <= n - 1
  • favorite[i] != i

Hints for Maximum Employees to Be Invited to a Meeting

  1. Hint 1

    Draw an edge from each employee to their favourite. Every component of this graph is one cycle with trees hanging into it.

  2. 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.

  3. 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

  1. Count in-degrees and queue everyone nobody favours (in-degree 0).
  2. Pop u, let v = favorite[u], set depth[v] = max(depth[v], depth[u] + 1), decrement v's in-degree and queue it at 0. Whatever is never popped lies on a cycle.
  3. Walk each remaining cycle once to get its length. For a 2-cycle (a, b) add 2 + depth[a] + depth[b] to a running pair total; for longer cycles track the maximum length.
  4. 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