2127. Maximum Employees to Be Invited to a Meeting

HardDepth-First SearchGraphTopological Sort

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.

Flowchart Walkthrough

First, let's go through the algorithm using the Flowchart. Here's a detailed process for determining the appropriate algorithm for LeetCode 2127. Maximum Employees to Be Invited to a Meeting:

Is it a graph?

Yes: The problem describes relationships between employees that can be visualized as a graph where each employee is a node, and their preferences represent directed edges from one employee to another.

Is it a tree?

No: The graph potentially contains cycles (employees can ultimately prefer themselves through a chain of preferences), indicating it is not a hierarchical tree structure.

Is the problem related to directed acyclic graphs (DAGs)?

No: We are dealing with potential cycles due to the nature of preferences, making it a cyclic graph, not acyclic.

Is the problem related to shortest paths?

No: The problem is to find the maximum number of employees that can attend the meeting, which doesn’t involve finding shortest paths.

Does the problem involve connectivity?

Yes: We are interested in the largest connected component, particularly the largest grouping where relationships/cycles of invitations exist.

Is the graph unweighted?

Yes: There are no weights involved in these relationships; it's merely about connectivity.

Conclusion: The flowchart suggests using DFS or BFS. Given the nature of needing to find cycles and understand the deepest connections, Depth-First Search (DFS) will be particularly useful for exploring each connected component deeply to find the maximum cycle or grouping that can be invited to a meeting.

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.

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 ans found so far.
To keep track of visited employees, it uses a boolean list vis.
It uses a greedy approach to always update the ans with 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 q with 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 distance dist to 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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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 ans is 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_sort function 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))
55

1class 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}
82

1class 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};
78

1// 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);
83

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know