Code Implementation

class Solution:
    def maximumInvitations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        match = [-1] * n

        def bpm(u, visited):
            for v in range(n):
                if grid[u][v] and not visited[v]:
                    visited[v] = True
                    if match[v] == -1 or bpm(match[v], visited):
                        match[v] = u
                        return True
            return False

        result = 0
        for u in range(m):
            visited = [False] * n
            if bpm(u, visited):
                result += 1
        return result
      

class Solution {
public:
    bool bpm(int u, vector<vector<int>>& grid, vector<int>& match, vector<bool>& visited) {
        int n = grid[0].size();
        for (int v = 0; v < n; ++v) {
            if (grid[u][v] && !visited[v]) {
                visited[v] = true;
                if (match[v] == -1 || bpm(match[v], grid, match, visited)) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int maximumInvitations(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> match(n, -1);
        int result = 0;
        for (int u = 0; u < m; ++u) {
            vector<bool> visited(n, false);
            if (bpm(u, grid, match, visited)) {
                ++result;
            }
        }
        return result;
    }
};
      

class Solution {
    public int maximumInvitations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] match = new int[n];
        Arrays.fill(match, -1);
        int result = 0;

        for (int u = 0; u < m; ++u) {
            boolean[] visited = new boolean[n];
            if (bpm(u, grid, match, visited)) {
                result++;
            }
        }
        return result;
    }
    private boolean bpm(int u, int[][] grid, int[] match, boolean[] visited) {
        int n = grid[0].length;
        for (int v = 0; v < n; ++v) {
            if (grid[u][v] == 1 && !visited[v]) {
                visited[v] = true;
                if (match[v] == -1 || bpm(match[v], grid, match, visited)) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
}
      

var maximumInvitations = function(grid) {
    const m = grid.length, n = grid[0].length;
    const match = new Array(n).fill(-1);

    function bpm(u, visited) {
        for (let v = 0; v < n; ++v) {
            if (grid[u][v] && !visited[v]) {
                visited[v] = true;
                if (match[v] === -1 || bpm(match[v], visited)) {
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    let result = 0;
    for (let u = 0; u < m; ++u) {
        const visited = new Array(n).fill(false);
        if (bpm(u, visited)) result++;
    }
    return result;
};
      

Problem Description

You are given a binary matrix grid of size m x n where grid[i][j] == 1 means the i-th boy can invite the j-th girl to the dance. Each boy can send an invitation to any number of girls, but each girl can accept at most one invitation, and each boy can have at most one invitation accepted. Your task is to find the maximum number of accepted invitations possible, such that no boy or girl is involved in more than one accepted invitation.

• Each invitation is from a boy to a girl (from row i to column j).
• No two invitations can involve the same boy or the same girl.
• Return the largest possible number of accepted invitations.

Thought Process

At first glance, this problem looks like matching up pairs between boys and girls based on who can invite whom. A brute-force approach would be to try every possible combination of invitations, but this quickly becomes infeasible as the numbers grow.

Instead, we recognize that this is a classic maximum bipartite matching problem. Each boy is a node on one side, each girl is a node on the other, and an edge exists if a boy can invite a girl. The goal is to find the maximum number of pairings such that no two pairings share a boy or a girl.

This is a well-known problem in graph theory, and efficient algorithms exist to solve it, such as the Hungarian Algorithm or using Depth-First Search (DFS) based augmentation.

Solution Approach

We model the problem as a bipartite graph:

• Left partition: Boys (rows of grid)
• Right partition: Girls (columns of grid)
• Edge between boy i and girl j if grid[i][j] == 1

The algorithm proceeds as follows:

1. For each boy, try to find a girl who can accept his invitation and is not already matched, or can be "reassigned" by recursively finding another match for her current boy.
2. We use a match array to keep track of which girl is matched with which boy.
3. For each boy, we use DFS to try to find an augmenting path: either an unmatched girl, or a girl whose current match can find another girl.
4. Each time we find an augmenting path, we increase the count of matches.

This approach is efficient and works well for the problem's constraints.

Example Walkthrough

Let's consider grid = [[1,1,0],[1,0,1],[0,0,1]]:

• Boy 0 can invite Girl 0 and Girl 1
• Boy 1 can invite Girl 0 and Girl 2
• Boy 2 can invite Girl 2

1. Start with Boy 0. Try Girl 0: unmatched, so match Girl 0 to Boy 0.
2. Next, Boy 1. Try Girl 0: already matched to Boy 0. Try to reassign Boy 0. Boy 0 can try Girl 1: unmatched, so match Girl 1 to Boy 0, then Girl 0 to Boy 1. Now, Girl 0 is matched to Boy 1, Girl 1 to Boy 0.
3. Boy 2 tries Girl 2: unmatched, so match Girl 2 to Boy 2.

Final matches: (Boy 0, Girl 1), (Boy 1, Girl 0), (Boy 2, Girl 2). Total = 3 accepted invitations.

Time and Space Complexity

Brute-force: Would require checking all possible combinations, which is exponential and infeasible for large grids.

Optimized (DFS-based matching):

• Let m be the number of boys, n the number of girls.
• For each boy, we may visit all girls, and for each girl, we may recursively visit all boys. In the worst case, time complexity is O(m * n) for a dense graph.
• Space complexity: O(n) for the match array and visited array.

Summary

The problem reduces to finding the maximum matching in a bipartite graph. By modeling boys and girls as two sets of nodes and using DFS-based augmentation, we efficiently pair as many boys and girls as possible, ensuring that no one is paired more than once. This approach is both elegant and efficient, leveraging classic graph algorithms to solve a real-world matching scenario.