2127. Maximum Employees to Be Invited to a Meeting
Problem Description
A company is planning a meeting and plans to have their employees sit at a large circular table. Every employee has a number, starting from 0 up to n-1, and each one also has a favorite coworker whom they want to be seated next to. The twist is that an employee will only come to the meeting if they can be seated next to their favorite personโhowever, note that no one can have themselves as their favorite. The objective is to find out the maximum number of employees that can be invited to the meeting where the seating arrangement satisfies everyone's preference of sitting next to their favorite person.
Intuition
To solve this problem, we're looking at a graph theory perspective where each employee can be seen as a node, and their preference of next person forms a directed edge to another node (employee). There are essentially two scenarios in which employees can be happy with the arrangement:
-
Cycles in the Graph: If the favorite preferences form a cycle, everyone in the cycle can be seated next to their favorite person. We need to find the longest cycle, as that would allow for the maximum number of employees to be seated.
-
Chains Leading into Cycles: If there's a cycle of just two people who have each other as favorites, employees can form a chain leading into this pair. The pair counts as 2 toward the total, and each chain leading into the pair adds 1 more employee to the total. It is necessary to consider chains that lead only into cycles of length two because longer cycles will already include employees being seated next to their favorite person.
Combining these two approaches gives us the maximum number of people that can be invited. To do that, we use two functions, max_cycle to handle the first scenario and topological_sort for the second. The max_cycle function finds the largest cycle, and the topological_sort function finds the longest chain that leads into any of the two-person cycles. The final answer is the maximum of the two results from these functions. By using topological sorting, we ensure that we count the longest path leading to a node, ensuring employees are sitting next to their favorite person.
Learn more about Depth-First Search, Graph and Topological Sort patterns.
Which of the following uses divide and conquer strategy?
Solution Approach
The given Python solution consists of two functions, max_cycle and topological_sort, each of which addresses the problem's two scenarios as explained earlier.
max_cycle Function:
- For each unvisited employee
i, this function finds a cycle using a while loop that continues until an already visited node is found, constructing the path it has traversed. - Once it reaches an employee that has been visited, it checks for a cycle by looking for the repeated employee in the path list. If found, it calculates the cycle's length and updates the maximal cycle length
ansfound so far. - To keep track of visited employees, it uses a boolean list
vis. - It uses a greedy approach to always update the
answith the largest cycle found.
topological_sort Function:
- It counts the incoming edges (preferences towards each employee) and initializes them in the list
indeg. - It also initializes a queue
qwith all employees who have zero incoming edges (meaning no one prefers them), which indicates they are at the start of a chain. - It processes each employee in
q, updating the distancedistto the maximum of the current or one more than the distance of the employee that prefers this one. - It decrements the incoming edge count for the person who is preferred, and if that drops to zero (meaning all preferring paths have been considered), the preferred employee is added to
q. - Note that only chains that lead into two-person cycles are considered in the final score, which is why the result is the sum of distances for such cases.
The solution's final answer comes from taking the maximum value between the longest cycle found by max_cycle and the sum of the longest chains leading into two-person cycles computed by topological_sort. The combination of these two gives us the maximum number of employees that can be invited to the meeting as per the given preferences.
Data Structures:
- A Boolean list
vis- To keep track of visited nodes while searching for cycles. - Integers list
indeg- To track the number of incoming preferences for each employee. - Integers list
dist- To track the maximum chain length leading to each node. - Queue
q- To efficiently process nodes in the topological sort once all incoming edges have been accounted for.
Algorithms:
- Cycle Detection: Detects cycles in the graph and finds the largest length (DFS approach).
- Topological Sorting: Used to process nodes with zero incoming edges and find the longest path from the start of a chain to a two-person cycle.
Which type of traversal does breadth first search do?
Example Walkthrough
Let's consider a small example with 5 employees where their favorite coworkers' indices are represented in the array favorites = [1, 2, 3, 4, 0]. This means employee 0's favorite is employee 1, employee 1's favorite is employee 2, and so on, forming a single cycle (0 โ 1 โ 2 โ 3 โ 4 โ 0). Using our approach:
Cycle detection using max_cycle function:
- Starting from employee 0, we find a cycle using the given preferences: 0's favorite is 1, 1's favorite is 2, 2's favorite is 3, 3's favorite is 4, and 4's favorite is 0.
- This forms a cycle of length 5, so
ansis set to 5, and all these employees are marked as visited.
Since this example contains a single cycle with all employees, there are no individual chains leading into a cycle, and the cycle itself satisfies everyone's preference without additional chains.
Chains leading into cycles using topological_sort function:
- However, if we consider a different set of preferences such as
favorites = [1, 2, 0, 4, 5, 3], we have a 3-employee cycle (3 โ 4 โ 5 โ 3), and the rest form chains leading into other employees. - The
topological_sortfunction wouldn't add anything to the result here, as we don't have any two-person cycles to which chains can lead into and we just use the cycle of length 3 for the final result.
In this example, using the max_cycle function gives us the result, and there's no need for the topological_sort function. Therefore, the maximum number of employees that can be invited to the meeting where the arrangement satisfies everyone is 5, corresponding to the length of the largest cycle detected.
Solution Implementation
1from typing import List
2from collections import deque
3
4class Solution:
5 def maximumInvitations(self, favorite: List[int]) -> int:
6 # Helper function to find the length of the largest cycle
7 def max_cycle(favorites):
8 n = len(favorites)
9 visited = [False] * n
10 max_ans = 0
11
12 # Iterate over all students
13 for i in range(n):
14 if visited[i]:
15 continue
16 cycle = []
17 j = i
18 # Build the cycle starting from student i
19 while not visited[j]:
20 cycle.append(j)
21 visited[j] = True
22 j = favorites[j]
23
24 # Detect the cycle length
25 for k, v in enumerate(cycle):
26 if v == j:
27 max_ans = max(max_ans, len(cycle) - k)
28 break
29 return max_ans
30
31 # Helper function to perform topological sort and find the longest path in the graph
32 def topological_sort(favorites):
33 n = len(favorites)
34 indegree = [0] * n
35 longest_path = [1] * n
36 # Create indegree array
37 for v in favorites:
38 indegree[v] += 1
39 # Queue for zero indegree students
40 queue = deque([i for i, d in enumerate(indegree) if d == 0])
41
42 # Perform BFS
43 while queue:
44 current = queue.popleft()
45 longest_path[favorites[current]] = max(longest_path[favorites[current]], longest_path[current] + 1)
46 indegree[favorites[current]] -= 1
47 if indegree[favorites[current]] == 0:
48 queue.append(favorites[current])
49
50 # Sum the distances of mutually favorite pairs
51 return sum(longest_path[i] for i, v in enumerate(favorites) if i == favorites[favorites[i]])
52
53 # Return the maximum value among the longest cycle and the result of the topological sort
54 return max(max_cycle(favorite), topological_sort(favorite))
551class Solution {
2 public int maximumInvitations(int[] favorite) {
3 // The solution is the maximum between the maximum cycle length
4 // and the result from the topological sorting.
5 return Math.max(findMaxCycle(favorite), topologicalSort(favorite));
6 }
7
8 // Helper method to find the length of the maximum cycle
9 private int findMaxCycle(int[] favorites) {
10 int n = favorites.length;
11 boolean[] visited = new boolean[n]; // To keep track of visited nodes
12 int maxCycleSize = 0; // Store the size of the longest cycle
13
14 // Iterate through each node to find cycles
15 for (int startNode = 0; startNode < n; ++startNode) {
16 if (visited[startNode]) {
17 // If the node is already visited, skip it
18 continue;
19 }
20 List<Integer> cycle = new ArrayList<>(); // To store the current cycle
21 int currentNode = startNode;
22
23 // Traverse the graph until a cycle is formed
24 while (!visited[currentNode]) {
25 cycle.add(currentNode);
26 visited[currentNode] = true;
27 currentNode = favorites[currentNode];
28 }
29
30 // Check if current node is part of the cycle
31 for (int k = 0; k < cycle.size(); ++k) {
32 if (cycle.get(k) == currentNode) {
33 // Update max cycle length if a longer cycle is found
34 maxCycleSize = Math.max(maxCycleSize, cycle.size() - k);
35 break;
36 }
37 }
38 }
39 return maxCycleSize;
40 }
41
42 // helper method to perform topological sorting and find the maximum length
43 private int topologicalSort(int[] favorites) {
44 int n = favorites.length;
45 int[] inDegree = new int[n]; // To keep track of in-degrees
46 int[] distance = new int[n]; // To keep track of max distances to each node
47 Arrays.fill(distance, 1); // Initialize distances to 1
48 for (int favorite : favorites) {
49 inDegree[favorite]++;
50 }
51
52 Deque<Integer> queue = new ArrayDeque<>(); // Queue for BFS
53 // Adding all nodes with in-degree 0 to the queue
54 for (int i = 0; i < n; ++i) {
55 if (inDegree[i] == 0) {
56 queue.offer(i);
57 }
58 }
59
60 while (!queue.isEmpty()) {
61 int currentNode = queue.poll();
62 int nextNode = favorites[currentNode];
63 // Update the distance for the next node
64 distance[nextNode] = Math.max(distance[nextNode], distance[currentNode] + 1);
65 // Reduce in-degree and add the next node to queue if its in-degree becomes 0
66 if (--inDegree[nextNode] == 0) {
67 queue.offer(nextNode);
68 }
69 }
70
71 int answer = 0;
72 // Look for pairs of nodes and sum up distances for pairs
73 // that are mutually pointing to each other
74 for (int i = 0; i < n; ++i) {
75 if (i == favorites[favorites[i]]) {
76 answer += distance[i];
77 }
78 }
79 return answer;
80 }
81}
821class Solution {
2public:
3 // Entry function that calculates the maximum number of invitations.
4 int maximumInvitations(vector<int>& favorite) {
5 // Determine the maximum between the longest cycle in the graph and
6 // the maximum sum of two paths stemming from a mutual favorite pair.
7 return max(findMaxCycle(favorite), topologicalSortAndPairSum(favorite));
8 }
9
10 // Function to find the maximum length of a cycle in the graph.
11 int findMaxCycle(vector<int>& favorites) {
12 int numStudents = favorites.size();
13 vector<bool> visited(numStudents, false);
14 int maxCycleLength = 0;
15
16 // Iterate through all students.
17 for (int i = 0; i < numStudents; ++i) {
18 if (visited[i]) continue;
19 vector<int> cycle;
20 int current = i;
21
22 // Identify a cycle starting from student 'i'.
23 while (!visited[current]) {
24 cycle.push_back(current);
25 visited[current] = true;
26 current = favorites[current];
27 }
28
29 // Check if the identified cycle contains 'j' and calculate the cycle's length.
30 for (int k = 0; k < cycle.size(); ++k) {
31 if (cycle[k] == current) {
32 maxCycleLength = max(maxCycleLength, (int)cycle.size() - k);
33 break;
34 }
35 }
36 }
37 return maxCycleLength;
38 }
39
40 // Function to perform topological sort and sum the distances of mutual favorite pairs.
41 int topologicalSortAndPairSum(vector<int>& favorites) {
42 int numStudents = favorites.size();
43 vector<int> inDegree(numStudents, 0);
44 vector<int> distance(numStudents, 1);
45
46 // Calculate in-degrees of the students.
47 for (int fav : favorites) ++inDegree[fav];
48
49 queue<int> queue;
50
51 // Enqueue students with an in-degree of 0.
52 for (int i = 0; i < numStudents; ++i) {
53 if (inDegree[i] == 0) queue.push(i);
54 }
55
56 // Perform topological sort.
57 while (!queue.empty()) {
58 int current = queue.front();
59 queue.pop();
60 distance[favorites[current]] = max(distance[favorites[current]], distance[current] + 1);
61
62 // Reduce the in-degree of the current node's favorite and enqueue if it becomes 0.
63 if (--inDegree[favorites[current]] == 0) {
64 queue.push(favorites[current]);
65 }
66 }
67
68 int pairSum = 0;
69 // Calculate the total sum of distances for mutually favorite pairs.
70 for (int i = 0; i < numStudents; ++i) {
71 if (i == favorites[favorites[i]]) {
72 pairSum += distance[i];
73 }
74 }
75 return pairSum;
76 }
77};
781// Type declaration for easier readability
2type FavoritesList = number[];
3
4// Calculates the maximum number of invitations.
5function maximumInvitations(favorites: FavoritesList): number {
6 // Determine the maximum between the longest cycle in the graph and
7 // the maximum sum of two paths stemming from a mutual favorite pair.
8 return Math.max(findMaxCycle(favorites), topologicalSortAndPairSum(favorites));
9}
10
11// Function to find the maximum length of a cycle in the graph.
12function findMaxCycle(favorites: FavoritesList): number {
13 const numStudents: number = favorites.length;
14 const visited: boolean[] = new Array(numStudents).fill(false);
15 let maxCycleLength: number = 0;
16
17 // Iterate through all students.
18 for (let i = 0; i < numStudents; ++i) {
19 if (visited[i]) continue;
20 const cycle: number[] = [];
21 let current: number = i;
22
23 // Identify a cycle starting from student 'i'.
24 while (!visited[current]) {
25 cycle.push(current);
26 visited[current] = true;
27 current = favorites[current];
28 }
29
30 // Check if the identified cycle contains 'j' and calculate the cycle's length.
31 for (let k = 0; k < cycle.length; ++k) {
32 if (cycle[k] === current) {
33 maxCycleLength = Math.max(maxCycleLength, cycle.length - k);
34 break;
35 }
36 }
37 }
38 return maxCycleLength;
39}
40
41// Function to perform topological sort and sum the distances of mutual favorite pairs.
42function topologicalSortAndPairSum(favorites: FavoritesList): number {
43 const numStudents: number = favorites.length;
44 const inDegree: number[] = new Array(numStudents).fill(0);
45 const distance: number[] = new Array(numStudents).fill(1);
46
47 // Calculate in-degrees of the students.
48 for (const fav of favorites) {
49 inDegree[fav]++;
50 }
51
52 const queue: number[] = [];
53
54 // Enqueue students with an in-degree of 0.
55 for (let i = 0; i < numStudents; ++i) {
56 if (inDegree[i] === 0) queue.push(i);
57 }
58
59 // Perform topological sort.
60 while (queue.length > 0) {
61 const current: number = queue.shift()!;
62 distance[favorites[current]] = Math.max(distance[favorites[current]], distance[current] + 1);
63
64 // Reduce the in-degree of the current node's favorite and enqueue if it becomes 0.
65 if (--inDegree[favorites[current]] === 0) {
66 queue.push(favorites[current]);
67 }
68 }
69
70 let pairSum: number = 0;
71 // Calculate the total sum of distances for mutually favorite pairs.
72 for (let i = 0; i < numStudents; ++i) {
73 if (i === favorites[favorites[i]]) {
74 pairSum += distance[i];
75 }
76 }
77 return pairSum;
78}
79
80// Example of usage
81// let favoritesList: FavoritesList = [...]; // Replace with actual list of favorites.
82// let maxInvitations: number = maximumInvitations(favoritesList);
83What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
Time and Space Complexity
The algorithm consists of two main functions: max_cycle and topological_sort. Let's analyze each regarding their time and space complexity.
max_cycle function
This function is looped once for each node in the range of n (n being the number of people in the circle). Inside the loop, it keeps track of the cycle using a while loop, which in the worst case could visit each node at most once. Thus, in the worst case, the while loop runs a total of n times for the entire function call, making it an O(n) operation.
Given that the maximum length of a cycle in a single directed graph without self-loops and multiple edges is n, and since we visit every node once, the space complexity for storing the cycles (using the cycle list) will also be O(n), plus O(n) for the vis list, resulting in an overall O(n) space complexity.
Time Complexity: O(n) Space Complexity: O(n)
topological_sort function
In the topological sort function, we first calculate the indegrees which is an O(n) operation. Then we perform a modified BFS using a deque to compute the longest path. Every node and edge is visited exactly once in this process, so it operates in O(n) time.
During the course of the BFS, the dist array is updated. This array has a length of n, hence the space required is O(n). The queue q in the worst case could also grow to hold n elements (when all nodes have 0 indegree).
Time Complexity: O(n) Space Complexity: O(n)
Overall Complexity
Since both functions run sequentially, the overall time complexity will be max(O(n), O(n)), which simplifies to O(n).
For space complexity, since the arrays used in both functions do not exist simultaneously and are not dependent on one another (they're used during separate function calls and hence the space for one can be reused for the other), the overall space complexity is also O(n), as it's the max space used at any one time, not the sum of space used.
Overall Time Complexity: O(n) Overall Space Complexity: O(n)
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.