Maximum employees to be invited to a meeting

Array Dynamic Programming Depth-First Search Graph Theory Topological Sort

61.8% acceptance

Feb 25, 2026

1676

A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees. The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself. Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_invitations(favorite: Vec<i32>) -> i32 {
    let n = favorite.len();

    // Compute in-degrees
    let mut in_deg = vec![0i32; n];
    for &f in &favorite {
      in_deg[f as usize] += 1;
    }

    // Topological sort to compute depth of tree chains (non-cycle nodes)
    let mut queue = std::collections::VecDeque::new();
    for i in 0..n {
      if in_deg[i] == 0 {
        queue.push_back(i);
      }
    }
    let mut depth = vec![0i32; n];
    let mut on_cycle = vec![true; n];

    while let Some(u) = queue.pop_front() {
      on_cycle[u] = false;
      let v = favorite[u] as usize;
      depth[v] = depth[v].max(depth[u] + 1);
      in_deg[v] -= 1;
      if in_deg[v] == 0 {
        queue.push_back(v);
      }
    }

    // Find all cycles
    let mut visited = vec![false; n];
    let mut max_large_cycle = 0i32;
    let mut sum_small_cycles = 0i32;

    for i in 0..n {
      if on_cycle[i] && !visited[i] {
        // Trace cycle
        let mut cycle_len = 0i32;
        let mut j = i;
        while !visited[j] {
          visited[j] = true;
          j = favorite[j] as usize;
          cycle_len += 1;
        }
        if cycle_len == 2 {
          // 2-cycle (mutual pair): can include long chains from trees
          let u = i;
          let v = favorite[i] as usize;
          sum_small_cycles += 2 + depth[u] + depth[v];
        } else {
          max_large_cycle = max_large_cycle.max(cycle_len);
        }
      }
    }

    max_large_cycle.max(sum_small_cycles)
  }
}