Leetcode 1820. Maximum Number of Accepted Invitations Solution
Problem Explanation
In this problem, we have m boys and n girls in a class attending an upcoming party. We are given a matrix grid, where grid[i][j] is either 0 or 1. If grid[i][j] equals 1, then the i-th boy can invite the j-th girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy. Our task is to return the maximum possible number of accepted invitations.
Approach
We can solve this problem using the Maximum Bipartite Matching algorithm (also known as the Hungarian Algorithm). It is an algorithm to find the maximum cardinality matching in a bipartite graph.
In the problem, each boy can invite a girl, so boys and girls make up two disjoint sets, and we can model them with a bipartite graph. The goal is to find a maximum number of accepted invitations, which means finding the maximum matching in the bipartite graph.
Let's walk through Example 1:
1grid = [ 2 [1, 1, 1], 3 [1, 0, 1], 4 [0, 0, 1] 5]
- Initially, all girls are not matched to any boy, so we have
mate = [-1, -1, -1]. - Now, for each boy, we try to find a girl that can be matched (invited). We start with the first boy, who can invite either the first or the second girl. To simplify the explanation, let's assume he invites the first girl. Now,
mate = [0, -1, -1]. - We move to the second boy, who can also invite either the first or the third girl. Since the first girl is already matched, she cannot accept another invitation, so the second boy invites the second girl. Now, we have
mate = [0, 1, -1]. - Lastly, we move to the third boy, who can only invite the third girl. As the third girl is not matched so far, she accepts the invitation. Now, we have
mate = [0, 1, 2]. - There are no more boys to process, so we return the number of matched girls - which is 3 in this case.
Python Solution
1class Solution:
2 def maximumInvitations(self, grid: List[List[int]]) -> int:
3 def canInvite(i: int, seen: List[bool], mate: List[int]) -> bool:
4 for j in range(len(seen)):
5 if not grid[i][j] or seen[j]:
6 continue
7 seen[j] = True
8 if mate[j] == -1 or canInvite(mate[j], seen, mate):
9 mate[j] = i # Match girl j with boy i.
10 return True
11 return False
12
13 m, n = len(grid), len(grid[0])
14 ans = 0
15 mate = [-1] * n # girl's mate
16
17 for i in range(m):
18 if canInvite(i, [False] * n, mate):
19 ans += 1
20
21 return ans
Java Solution
1import java.util.Arrays;
2
3class Solution {
4 public int maximumInvitations(int[][] grid) {
5 int m = grid.length;
6 int n = grid[0].length;
7 int ans = 0;
8 int[] mate = new int[n];
9 Arrays.fill(mate, -1); // girl's mate
10
11 for (int i = 0; i < m; ++i) {
12 if (canInvite(grid, i, new boolean[n], mate)) {
13 ++ans;
14 }
15 }
16
17 return ans;
18 }
19
20 private boolean canInvite(int[][] grid, int i, boolean[] seen, int[] mate) {
21 for (int j = 0; j < seen.length; ++j) {
22 if (grid[i][j] == 0 || seen[j]) {
23 continue;
24 }
25 seen[j] = true;
26 if (mate[j] == -1 || canInvite(grid, mate[j], seen, mate)) {
27 mate[j] = i; // Match girl j with boy i.
28 return true;
29 }
30 }
31
32 return false;
33 }
34}
JavaScript Solution
1class Solution {
2 maximumInvitations(grid) {
3 const m = grid.length;
4 const n = grid[0].length;
5 let ans = 0;
6 const mate = new Array(n).fill(-1); // girl's mate
7
8 for (let i = 0; i < m; ++i) {
9 if (this.canInvite(grid, i, new Array(n).fill(false), mate)) {
10 ++ans;
11 }
12 }
13
14 return ans;
15 }
16
17 canInvite(grid, i, seen, mate) {
18 for (let j = 0; j < seen.length; ++j) {
19 if (grid[i][j] === 0 || seen[j]) {
20 continue;
21 }
22 seen[j] = true;
23 if (mate[j] === -1 || this.canInvite(grid, mate[j], seen, mate)) {
24 mate[j] = i; // Match girl j with boy i.
25 return true;
26 }
27 }
28
29 return false;
30 }
31}
C++ Solution
1#include <vector>
2
3class Solution {
4public:
5 int maximumInvitations(std::vector<std::vector<int>>& grid) {
6 int m = grid.size();
7 int n = grid[0].size();
8 int ans = 0;
9 std::vector<int> mate(n, -1); // girl's mate
10
11 for (int i = 0; i < m; ++i) {
12 if (canInvite(grid, i, std::vector<bool>(n), mate)) {
13 ++ans;
14 }
15 }
16
17 return ans;
18 }
19
20private:
21 bool canInvite(const std::vector<std::vector<int>>& grid, int i, std::vector<bool>&& seen,
22 std::vector<int>& mate) {
23 for (int j = 0; j < seen.size(); ++j) {
24 if (!grid[i][j] || seen[j]) {
25 continue;
26 }
27 seen[j] = true;
28 if (mate[j] == -1 || canInvite(grid, mate[j], std::move(seen), mate)) {
29 mate[j] = i; // Match girl j with boy i.
30 return true;
31 }
32 }
33
34 return false;
35 }
36};
C# Solution
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaximumInvitations(int[][] grid) {
6 int m = grid.Length;
7 int n = grid[0].Length;
8 int ans = 0;
9 int[] mate = new int[n];
10 Array.Fill(mate, -1); // girl's mate
11
12 for (int i = 0; i < m; ++i) {
13 if (CanInvite(grid, i, new bool[n], mate)) {
14 ++ans;
15 }
16 }
17
18 return ans;
19 }
20
21 private bool CanInvite(int[][] grid, int i, bool[] seen, int[] mate) {
22 for (int j = 0; j < seen.Length; ++j) {
23 if (grid[i][j] == 0 || seen[j]) {
24 continue;
25 }
26 seen[j] = true;
27 if (mate[j] == -1 || CanInvite(grid, mate[j], seen, mate)) {
28 mate[j] = i; // Match girl j with boy i.
29 return true;
30 }
31 }
32
33 return false;
34 }
35}
Time Complexity
The time complexity of the algorithm is O(m * n * n), where m is the number of boys and n is the number of girls. In each iteration of the outer loop, there is a call to canInvite, which in turn has two nested loops.
Space Complexity
The space complexity is O(m * n), as we need to store the grid and the state of the matching in each step (seen and mate).
Conclusion
In this problem, we used the Maximum Bipartite Matching algorithm to find the maximum number of matches between boys and girls based on their relationships. For Python, Java, JavaScript, C++ and C#, we presented a solution that has a time complexity of O(m * n * n) and space complexity of O(m * n), where m is the number of boys and n is the number of girls.