Maximum Number of Accepted Invitations

Intuition

This is a classic bipartite maximum matching problem: boys form one side, girls the other, and a 1 in the grid is an eligible edge. We process boys one by one and try to match each to some girl using a DFS. When a boy reaches a girl who is free, we pair them; if she is already taken, we recursively ask her current partner to step aside and find another girl. This chain of reassignments is called an augmenting path, and finding one increases the total matching by exactly one. Resetting the visited marks for each boy keeps every search independent, and the final count of successful searches is the maximum matching.

Algorithm walkthrough

1. 1Keep an array matchGirl where matchGirl[j] holds the boy currently paired with girl j, or -1 if she is unmatched.
2. 2Iterate over every boy and start a DFS with a fresh visited array over the girls.
3. 3In the DFS, scan each girl the boy can invite that has not been visited in this search, and mark her visited.
4. 4If that girl is free, or her current partner can be reassigned via a recursive DFS, pair her with the current boy and report success.
5. 5Each boy whose DFS succeeds increments the match count by one.
6. 6After all boys are processed, the accumulated count is the maximum number of accepted invitations.

Implementation

from typing import List

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

        def try_assign(boy: int, visited: List[bool]) -> bool:
            for girl in range(n):
                if grid[boy][girl] == 1 and not visited[girl]:
                    visited[girl] = True
                    if match_girl[girl] == -1 or try_assign(match_girl[girl], visited):
                        match_girl[girl] = boy
                        return True
            return False

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