1820. Maximum Number of Accepted Invitations


Problem Description

In this problem, we are presented with a class consisting of m boys and n girls who are planning to attend an upcoming party. Each boy can invite only one girl, and each girl can accept only one invitation from a boy.

We are given a grid represented as an m x n integer matrix. The cell grid[i][j] can either be 0 or 1. If grid[i][j] == 1, it means the i-th boy has the option to invite the j-th girl to the party. Our task is to find the maximum number of invitations that can be accepted under these conditions.

In other words, our objective is to pair as many boys with girls as possible, with the constraint that each boy can invite only one girl and each girl can accept only one boy's invitation.

Intuition

To tackle this problem, we can use a graph-based approach. We can create a bipartite graph from the grid, with boys on one side and girls on the other. An edge is drawn between a boy and a girl if the boy can invite that girl (grid[i][j] == 1). The solution to the problem is then to find the maximum matching in this bipartite graph, which represents the largest number of pairs (invitations) that can be formed without overlap.

The intuition behind finding the maximum matching is to iterate through each boy and try to find a girl that he can invite. If the girl is already invited by another boy, we then check if that other boy can invite a different girl. This process is similar to trying to find an augmenting path in the graph—a path that can increase the number of matched pairs.

The solution code defines a function find(i) which performs a depth-first search (DFS) for a given boy i. This function attempts to find an available girl or to rearrange the current matches (if a girl is already invited) such that everyone including boy i can have a match.

Inside the main function maximumInvitations, we maintain an array match where match[j] is the index of the boy who has invited girl j. We initialize all matches as -1, meaning initially, no girls have been invited. We also keep a count ans to keep track of the number of invitations successfully made.

The main function then iterates over each boy, trying to find a match for them using the find function while keeping track of visited girls in the vis set to avoid revisiting during the DFS of the current iteration. For each iteration, if a new match is found for the current boy, we increment the ans by 1.

In summary, the code employs a greedy depth-first search algorithm to iteratively build the maximum number of boy-girl pairings for the party invitations, following principles used to solve the maximum matching problem in bipartite graphs.

Solution Approach

The solution uses a depth-first search (DFS) algorithm to implement a technique often used for finding maximum matchings in bipartite graphs known as the Hungarian algorithm or the Ford-Fulkerson algorithm in its DFS version.

Here's a breakdown of the implementation:

Data Structures Used:

  • grid: An m x n matrix that represents available invitations, where m is the number of boys and n is the number of girls.
  • match: A list where match[j] stores the index of the boy who has currently invited the j-th girl. It has n elements, one for each girl.
  • vis: A set that keeps track of the visited girls in the current DFS iteration to prevent cycles and revisitations.

Algorithms and Patterns:

  1. Initialization:

    • Create the match list with all elements initialized to -1, representing that no invitations have been made yet.
  2. Main Loop:

    • Iterate through each boy, trying to find an invitation for them. For each iteration, create a new empty set vis to keep track of visited girls to ensure the DFS does not revisit nodes within the same path.
  3. DFS Function - find:

    • The find function attempts to find an invitation for boy i. It iterates through all the girls and checks two conditions for each girl j:
      • Whether boy i can invite girl j (indicated by grid[i][j] == 1).
      • Whether girl j is not already visited during the current DFS iteration (j not in vis).
    • If both conditions are met, it adds girl j to the set vis and checks if girl j is not matched (match[j] == -1) or if the boy currently matched with girl j can find an alternate girl (find(match[j])). In both of these cases, the current boy i can invite girl j, and we update the match[j] to i and return True.

Execution of the Algorithm:

  • For each boy, the DFS find function is called.
  • If a match is found (the find function returns True), the count ans is incremented by 1.
  • Finally, after the main loop has finished, the total count ans represents the maximum possible number of accepted invitations, which is returned as the result.

Essentially, the algorithm explores potential matches for each boy. When a potential match is found that either adds a new invitation or can replace an existing one (allowing the displaced boy to find another girl), it contributes to a larger number of overall invitations. Adjustments continue until no more matches can be made, ensuring the maximum number of invitations is reached.

The algorithm complexity is O(m * n * n), where the factor n * n comes from the find function, which, in the worst case, could be called for each girl (n) in each iteration for every boy (m).

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small example where we have a 3 x 3 grid representing 3 boys and 3 girls as follows:

1grid = [[1, 0, 1],
2        [0, 1, 0],
3        [1, 1, 1]]

Here, the 1st boy can invite either the 1st or the 3rd girl, the 2nd boy can invite the 2nd girl, and the 3rd boy can invite any of the girls.

Now, let's apply our solution approach to this example:

  1. We initialize our match array to -1, which gives us [-1, -1, -1], indicating no girl has received an invite yet.
  2. We set our ans (answer) count to 0 as no pairs have been formed yet.

We will now iterate through each boy and try to find a match using DFS:

  • Boy 1:
    • We attempt to invite Girl 1 since grid[0][0] == 1. Since Girl 1 has not been invited yet (match[0] == -1), we invite her, and our match array becomes [0, -1, -1].
    • We increment ans to 1 as a successful match has been made.
  • Boy 2:
    • Now we try to invite Girl 2 as grid[1][1] == 1. Again, she has not been invited yet (match[1] == -1), so we update the match array to [0, 1, -1].
    • The ans count is increased to 2.
  • Boy 3:
    • Boy 3 could invite Girl 1, 2, or 3 (since grid[2][0] == 1, grid[2][1] == 1, and grid[2][2] == 1). However, Girls 1 and 2 are already invited by Boys 1 and 2, so we have to check if we can rearrange.
    • We first try for Girl 1. Since Boy 1 can also invite Girl 3, we assign Girl 3 to Boy 1, rearranging the match to [0, 1, 0], and then assign Girl 1 to Boy 3, updating the match array to [2, 1, 0].
    • Notice that we had to backtrack and rearrange the existing pair to maximize the number of invitations.
    • The ans count is incremented to 3.

After iterating through all the boys, we find that the maximum number of invitations is 3, which is also the total number of boys in our example. Each girl has been matched with a boy, which is our optimal solution.

In this small example, the algorithm goes through each boy and ensures all possible matches are made by rearranging previous matches if necessary, which is in line with the DFS technique described. All boys are able to invite a girl, and this example therefore successfully illustrates the solution approach in practice.

Python Solution

1class Solution:
2    def maximumInvitations(self, grid: List[List[int]]) -> int:
3        # Helper function to find a match for a person from "group A"
4        def can_invite(person_from_a):
5            for colleague_index, has_relation in enumerate(grid[person_from_a]):
6                # Check if the current person from "group B" has not been visited and there's a relation
7                if has_relation and colleague_index not in visited:
8                    visited.add(colleague_index)
9                  
10                    # If the person from "group B" is not matched or can be matched to another person
11                    if matches[colleague_index] == -1 or can_invite(matches[colleague_index]):
12                        # Match person_from_a with colleague_index from "group B"
13                        matches[colleague_index] = person_from_a
14                        return True
15
16            # Return False if no match is found for person_from_a
17            return False
18
19        # Number of people in "group A" and "group B" (rows and columns of the grid)
20        num_people_a, num_people_b = len(grid), len(grid[0])
21      
22        # Initialize matches for each person in "group B" to -1 (indicating no matches)
23        matches = [-1] * num_people_b
24      
25        # Total number of matches (invitations) we can make
26        total_invitations = 0
27      
28        # Loop through each person in "group A" to find a matching person in "group B"
29        for person_from_a in range(num_people_a):
30            # Set of visited indices in "group B" for the current person from "group A"
31            visited = set()
32          
33            # If a match is found, increment the total number of invitations
34            if can_invite(person_from_a):
35                total_invitations += 1
36
37        # Return the total number of invitations
38        return total_invitations
39

Java Solution

1import java.util.Arrays;
2
3public class Solution {
4    private int[][] grid; // The grid representing invitations
5    private boolean[] visited; // To track if a column (person in right set) has been visited
6    private int[] matched; // To store matched left-side people to right-side people
7    private int columns; // Number of columns in the grid
8
9    // Method to compute the maximum number of invitations
10    public int maximumInvitations(int[][] grid) {
11        int rows = grid.length; // Number of rows in the grid
12        columns = grid[0].length; // Number of columns in the grid
13        this.grid = grid;
14        visited = new boolean[columns]; // Initialize visited array for tracking
15        matched = new int[columns]; // Initialize matches array
16        Arrays.fill(matched, -1); // Fill the matches array with -1 indicating no match
17        int invitations = 0; // Initialize invitation count
18
19        // Iterate over all rows (left side people) to find maximum matchings
20        for (int i = 0; i < rows; ++i) {
21            Arrays.fill(visited, false); // Reset the visited array for each iteration
22            if (tryFindMatch(i)) {
23                invitations++; // If a match is found, increment the invitation count
24            }
25        }
26        return invitations; // Return the maximum number of invitations
27    }
28
29    // Helper method to find a match for a person in the left set
30    private boolean tryFindMatch(int personIdx) {
31        for (int j = 0; j < columns; ++j) {
32            // If there's an invitation from personIdx to right set person 'j' and 'j' is not visited
33            if (grid[personIdx][j] == 1 && !visited[j]) {
34                visited[j] = true; // Mark 'j' as visited
35                // If 'j' is not matched, or we can find a match for 'j's current match
36                if (matched[j] == -1 || tryFindMatch(matched[j])) {
37                    matched[j] = personIdx; // Match personIdx (left set) with 'j' (right set)
38                    return true; // A match was successful
39                }
40            }
41        }
42        return false; // No match was found for personIdx
43    }
44}
45

C++ Solution

1#include <vector>
2#include <cstring>
3#include <functional>
4
5class Solution {
6public:
7    // Method to calculate the maximum number of invitations that can be sent.
8    int maximumInvitations(vector<vector<int>>& grid) {
9        int rowCount = grid.size();
10        int colCount = grid[0].size();
11      
12        // Initialize visitation status and match arrays.
13        bool visited[210];
14        int match[210];
15        memset(match, -1, sizeof(match));
16      
17        int totalInvitations = 0; // Counter for total invitations.
18      
19        // Lambda function to perform DFS and find if a match can be made for a row.
20        function<bool(int)> tryMatch = [&](int row) -> bool {
21            for (int col = 0; col < colCount; ++col) {
22                // If there's a potential match and column is not yet visited.
23                if (grid[row][col] && !visited[col]) {
24                    visited[col] = true;
25                  
26                    // If the column is not matched or the previously matched row can be matched elsewhere.
27                    if (match[col] == -1 || tryMatch(match[col])) {
28                        // Make the match and return true.
29                        match[col] = row;
30                        return true;
31                    }
32                }
33            }
34            return false; // No match found for this row.
35        };
36      
37        // Iterate over rows to find all possible matches.
38        for (int row = 0; row < rowCount; ++row) {
39            memset(visited, 0, sizeof(visited)); // Reset visitation status.
40            totalInvitations += tryMatch(row); // Increment if a match is found.
41        }
42      
43        return totalInvitations; // Return the total number of successful invitations.
44    }
45};
46

Typescript Solution

1const GRID_SIZE_LIMIT: number = 210;
2let grid: number[][] = [];
3let rowCount: number = 0;
4let colCount: number = 0;
5let visited: boolean[] = new Array(GRID_SIZE_LIMIT).fill(false);
6let match: number[] = new Array(GRID_SIZE_LIMIT).fill(-1);
7let totalInvitations: number = 0;
8
9// Function to calculate the maximum number of invitations that can be sent
10function maximumInvitations(inputGrid: number[][]): number {
11    grid = inputGrid;
12    rowCount = grid.length;
13    colCount = grid[0].length;
14    totalInvitations = 0;
15
16    // Reset match array for each new grid.
17    match.fill(-1);
18
19    // Iterate over rows to find all possible matches
20    for (let row = 0; row < rowCount; ++row) {
21        // Reset visitation status for each row
22        visited.fill(false);
23
24        // Increment if a match is found
25        if (tryMatch(row)) {
26            totalInvitations++;
27        }
28    }
29
30    // Return the total number of successful invitations
31    return totalInvitations;
32}
33
34// Recursive function to perform DFS and find if a match can be made for a row
35function tryMatch(row: number): boolean {
36    for (let col = 0; col < colCount; ++col) {
37        // If there's a potential match and column is not yet visited
38        if (grid[row][col] && !visited[col]) {
39            // Mark column as visited
40            visited[col] = true;
41
42            // If the column is not matched or the previously matched row can be matched elsewhere
43            if (match[col] === -1 || tryMatch(match[col])) {
44                // Make the match and return true
45                match[col] = row;
46                return true;
47            }
48        }
49    }
50
51    // No match found for this row
52    return false;
53}
54
55// Example usage:
56// const grid = [
57//   [1, 0, 0, 1],
58//   [1, 0, 0, 0],
59//   [0, 0, 1, 0],
60//   [0, 0, 1, 1]
61// ];
62// console.log(maximumInvitations(grid));
63

Time and Space Complexity

Time Complexity

The given code performs a modification of the Hungarian algorithm for the maximum bipartite matching problem. The time complexity is derived from the nested loops and the find function, which is a depth-first search (DFS):

  • There is an outer loop that iterates m times where m is the number of rows in grid. This loop calls the find function.

  • Within the find function, there is a loop that iterates n times in the worst case, where n is the number of columns, to try to find a matching for each element in the row.

  • The depth-first search (DFS) within the find function can traverse up to n elements in the worst-case scenario.

  • Since match[j] is called recursively within find (specifically, find(match[j])), in the worst case, this can lead to another n iterations if every column is linked to a new row. Hence, the recursive calls can happen n times in the worst case.

Combining these factors, the time complexity of the entire algorithm is O(m * n^2) in the worst case.

Space Complexity

The space complexity can be considered based on the data structures used:

  • The match list uses space proportional to n, which is O(n).

  • The vis set can store up to n unique values in the worst case, as it keeps track of the visited columns for each row during DFS. This also results in space complexity of O(n).

  • The recursive find function can go up to n levels deep due to recursive calls, which could potentially use space O(n) on the call stack.

As these do not depend on each other and only the maximum will determine the overall space complexity, the space complexity of the algorithm is O(n).

😈
Become an
Algo Monster

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.


TA 👨‍🏫