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:

1
2
3
4
5
6
7

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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 == m
  • grid[i].length == n
  • 1 <= m, n <= 200
  • grid[i][j] is either 0 or 1.

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

  1. Treat boys and girls as two sets in a bipartite graph.
  2. For each boy, try to find a girl he can invite who is not already matched, or whose current match can be reassigned.
  3. Use DFS to find an augmenting path for each boy.
  4. Track which girls are already matched.
  5. Count the total number of successful matches.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 total O(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.