MediumArrayDepth-First SearchGraphMatrix

Maximum Number of Accepted Invitations

1 approach, code in every language

There are m boys and n girls at a party, described by an m x n binary matrix grid. If grid[i][j] == 1, then boy i is allowed to invite girl j to dance; otherwise he cannot.

Each boy may invite at most one girl, and each girl may accept at most one invitation. You want to arrange the invitations so that as many dance pairs form as possible.

Return the maximum possible number of accepted invitations.

Example 1

Input: grid = [[1,1,1],[1,0,1],[0,0,1]]

Output: 3

Boy 0 invites girl 1, boy 1 invites girl 0, and boy 2 invites girl 2. All three invitations are accepted.

Example 2

Input: grid = [[1,0,1,0],[1,0,0,0],[0,0,1,0],[1,1,1,0]]

Output: 3

One optimal pairing is boy 0 -> girl 2, boy 1 -> girl 0, and boy 3 -> girl 1. Boy 2 shares girl 2 with boy 0, so only three matches are possible.

Constraints

grid.length == m
grid[i].length == n
1 <= m, n <= 200
grid[i][j] is either 0 or 1

Bipartite Matching (Augmenting Paths)

Model boys and girls as two sides of a bipartite graph and repeatedly search for augmenting paths to grow the matching one pair at a time.

Loading animation…

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

1Keep an array matchGirl where matchGirl[j] holds the boy currently paired with girl j, or -1 if she is unmatched.
2Iterate over every boy and start a DFS with a fresh visited array over the girls.
3In the DFS, scan each girl the boy can invite that has not been visited in this search, and mark her visited.
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.
5Each boy whose DFS succeeds increments the match count by one.
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

Time

O(V * E)

Space

O(V + E)

With V boys and E eligible edges, each augmenting-path search costs O(E), giving O(V * E) overall (about O(m * m * n) here).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free