Maximum Number of Accepted Invitations
MediumUpdated: Aug 2, 2025
Practice on:
Problem
There are m boys and n girls in a class attending an upcoming party.
You are given an m x n integer matrix grid, where grid[i][j] equals 0
or 1. If grid[i][j] == 1, then that means the ith boy can invite the
jth girl to the party. A boy can invite at mostone girl , and a girl can accept at most one invitation from a boy.
Return themaximum possible number of accepted invitations.
Examples
Example 1:
Input: grid = [[1,1,1],
[1,0,1],
[0,0,1]]
Output: 3Explanation: The invitations are sent as follows:
- The 1st boy invites the 2nd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites the 3rd girl.
Example 2:
Input: grid = [[1,0,1,0],
[1,0,0,0],
[0,0,1,0],
[1,1,1,0]]
Output: 3
Explanation: The invitations are sent as follows:
-The 1st boy invites the 3rd girl.
-The 2nd boy invites the 1st girl.
-The 3rd boy invites no one.
-The 4th boy invites the 2nd girl.
Constraints:
grid.length == mgrid[i].length == n1 <= m, n <= 200grid[i][j]is either0or1.
Solution
Method 1 – Bipartite Matching (DFS)
Intuition
The problem is about finding the maximum number of unique boy-girl pairs such that each boy invites at most one girl and each girl accepts at most one invitation. This is a classic bipartite matching problem, where boys and girls form two sets, and an edge exists if a boy can invite a girl. We use DFS to find augmenting paths and maximize the number of matches.
Approach
- Treat boys and girls as two sets in a bipartite graph.
- For each boy, try to find a girl he can invite who is not already matched, or whose current match can be reassigned.
- Use DFS to find an augmenting path for each boy.
- Track which girls are already matched.
- Count the total number of successful matches.
Code
C++
class Solution {
public:
int maximumInvitations(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), ans = 0;
vector<int> match(n, -1);
function<bool(int, vector<bool>&)> dfs = [&](int u, vector<bool>& vis) {
for (int v = 0; v < n; ++v) {
if (grid[u][v] && !vis[v]) {
vis[v] = true;
if (match[v] == -1 || dfs(match[v], vis)) {
match[v] = u;
return true;
}
}
}
return false;
};
for (int u = 0; u < m; ++u) {
vector<bool> vis(n);
if (dfs(u, vis)) ++ans;
}
return ans;
}
};
Go
func maximumInvitations(grid [][]int) int {
m, n := len(grid), len(grid[0])
match := make([]int, n)
for i := range match {
match[i] = -1
}
var dfs func(int, []bool) bool
dfs = func(u int, vis []bool) bool {
for v := 0; v < n; v++ {
if grid[u][v] == 1 && !vis[v] {
vis[v] = true
if match[v] == -1 || dfs(match[v], vis) {
match[v] = u
return true
}
}
}
return false
}
ans := 0
for u := 0; u < m; u++ {
vis := make([]bool, n)
if dfs(u, vis) {
ans++
}
}
return ans
}
Java
class Solution {
public int maximumInvitations(int[][] grid) {
int m = grid.length, n = grid[0].length, ans = 0;
int[] match = new int[n];
Arrays.fill(match, -1);
for (int u = 0; u < m; u++) {
boolean[] vis = new boolean[n];
if (dfs(u, grid, match, vis)) ans++;
}
return ans;
}
private boolean dfs(int u, int[][] grid, int[] match, boolean[] vis) {
for (int v = 0; v < grid[0].length; v++) {
if (grid[u][v] == 1 && !vis[v]) {
vis[v] = true;
if (match[v] == -1 || dfs(match[v], grid, match, vis)) {
match[v] = u;
return true;
}
}
}
return false;
}
}
Kotlin
class Solution {
fun maximumInvitations(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val match = IntArray(n) { -1 }
fun dfs(u: Int, vis: BooleanArray): Boolean {
for (v in 0 until n) {
if (grid[u][v] == 1 && !vis[v]) {
vis[v] = true
if (match[v] == -1 || dfs(match[v], vis)) {
match[v] = u
return true
}
}
}
return false
}
var ans = 0
for (u in 0 until m) {
val vis = BooleanArray(n)
if (dfs(u, vis)) ans++
}
return ans
}
}
Python
class Solution:
def maximumInvitations(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
match = [-1] * n
def dfs(u: int, vis: list[bool]) -> bool:
for v in range(n):
if grid[u][v] and not vis[v]:
vis[v] = True
if match[v] == -1 or dfs(match[v], vis):
match[v] = u
return True
return False
ans = 0
for u in range(m):
vis = [False] * n
if dfs(u, vis):
ans += 1
return ans
Rust
impl Solution {
pub fn maximum_invitations(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut match_girl = vec![-1; n];
fn dfs(u: usize, grid: &Vec<Vec<i32>>, match_girl: &mut Vec<i32>, vis: &mut Vec<bool>) -> bool {
for v in 0..grid[0].len() {
if grid[u][v] == 1 && !vis[v] {
vis[v] = true;
if match_girl[v] == -1 || dfs(match_girl[v] as usize, grid, match_girl, vis) {
match_girl[v] = u as i32;
return true;
}
}
}
false
}
let mut ans = 0;
for u in 0..m {
let mut vis = vec![false; n];
if dfs(u, &grid, &mut match_girl, &mut vis) {
ans += 1;
}
}
ans
}
}
TypeScript
class Solution {
maximumInvitations(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
const match = Array(n).fill(-1);
const dfs = (u: number, vis: boolean[]): boolean => {
for (let v = 0; v < n; v++) {
if (grid[u][v] && !vis[v]) {
vis[v] = true;
if (match[v] === -1 || dfs(match[v], vis)) {
match[v] = u;
return true;
}
}
}
return false;
};
let ans = 0;
for (let u = 0; u < m; u++) {
const vis = Array(n).fill(false);
if (dfs(u, vis)) ans++;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(m * n)per boy, so totalO(m * n^2)– for each boy, we may visit all girls, and for each girl, we may traverse up to all boys in the worst case. - 🧺 Space complexity:
O(m + n)– for the match array and visited array per DFS call.