LeetCode 1820 - Maximum Number of Accepted Invitations

This problem asks us to maximize the number of successful invitations between boys and girls under a one-to-one matching constraint. We are given an m x n binary matrix called grid.

leetcodemediumarraydepth-first-searchgraph-theorymatrix

LeetCode Problem 1820

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Graph Theory, Matrix

Solution

Problem Understanding

This problem asks us to maximize the number of successful invitations between boys and girls under a one-to-one matching constraint.

We are given an m x n binary matrix called grid.

  • grid[i][j] == 1 means boy i is willing or able to invite girl j
  • grid[i][j] == 0 means boy i cannot invite girl j

Each boy can invite at most one girl, and each girl can accept at most one invitation. The goal is to determine the largest number of pairings that can exist simultaneously without conflicts.

This is fundamentally a matching problem on a bipartite graph.

We can think of:

  • Boys as nodes on the left side
  • Girls as nodes on the right side
  • A 1 in the matrix as an edge between them

The task becomes finding the maximum number of edges such that no two chosen edges share the same endpoint. This is exactly the definition of a maximum bipartite matching.

The constraints are important:

  • 1 <= m, n <= 200
  • Total possible edges can be up to 200 * 200 = 40,000

A brute-force search over all possible assignments would be completely infeasible because the number of combinations grows exponentially.

Some important edge cases include:

  • A matrix filled with zeros, where no invitations are possible
  • A matrix filled with ones, where the answer becomes min(m, n)
  • Multiple boys competing for the same girl
  • Situations where a greedy assignment fails, because reassigning earlier matches is necessary to achieve the optimal result

The last point is especially important. A naive greedy strategy can easily get stuck in a suboptimal configuration.

Approaches

Brute Force Approach

A brute-force solution would try every possible assignment of girls to boys.

For each boy, we could:

  • Skip assigning a girl
  • Try every available girl that the boy can invite

Then recursively continue to the next boy while tracking which girls are already taken.

This approach guarantees correctness because it explores every valid matching configuration and keeps the maximum size found.

However, it is far too slow.

In the worst case, each boy could potentially match with many girls, leading to an exponential number of possibilities. Even with pruning, the search space becomes enormous when m and n approach 200.

Optimal Approach

The key observation is that this problem is a classic maximum bipartite matching problem.

Instead of trying every assignment globally, we can iteratively build a matching using augmenting paths.

The idea is:

  • Try to match each boy with a girl
  • If the desired girl is already matched, try to reassign the currently matched boy to another girl
  • If reassignment succeeds, we free the girl and increase the total matching size

This is commonly implemented using Depth-First Search.

The DFS searches for an augmenting path, which is a sequence of reassignments that increases the total number of matches by one.

Because the graph size is relatively small, the standard DFS-based Kuhn algorithm is efficient enough.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Tries every possible assignment
Optimal O(m × n × m) O(n) Bipartite matching using DFS augmenting paths

Algorithm Walkthrough

Step 1: Model the Problem as a Bipartite Graph

Treat:

  • Each boy as a node on the left side
  • Each girl as a node on the right side
  • Each 1 in the matrix as an edge

We want the maximum number of non-overlapping edges.

Step 2: Maintain Current Girl Assignments

Create an array called girl_match.

  • girl_match[g] = b means girl g is currently matched with boy b
  • Initialize all entries to -1, meaning no girl is matched initially

This structure lets us quickly determine whether a girl is free.

Step 3: Attempt to Match Each Boy

Iterate through every boy.

For each boy, run DFS to try finding an augmenting path.

If DFS succeeds, increment the answer because we successfully added one more match.

Step 4: DFS Searches for an Augmenting Path

Inside DFS:

  1. Iterate through all girls
  2. Skip girls that this boy cannot invite
  3. Skip girls already visited during the current DFS call

For each valid girl:

  • Mark her as visited
  • If she is unmatched, assign her immediately
  • Otherwise, recursively try to rematch her current boy elsewhere

If rematching succeeds:

  • Assign the current girl to the new boy
  • Return True

Otherwise continue searching.

Step 5: Repeat Until All Boys Are Processed

Every successful DFS increases the matching size by exactly one.

After processing all boys, the answer is the maximum number of accepted invitations.

Why it works

The algorithm works because every DFS searches for an augmenting path.

An augmenting path rearranges existing assignments in a way that increases the total number of matches by one. Repeatedly applying augmenting paths is a standard theorem in bipartite matching theory, which guarantees that when no more augmenting paths exist, the matching is maximum.

Python Solution

from typing import List

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

        girl_match = [-1] * n

        def dfs(boy: int, visited: List[bool]) -> bool:
            for girl in range(n):
                if grid[boy][girl] == 0 or visited[girl]:
                    continue

                visited[girl] = True

                if girl_match[girl] == -1:
                    girl_match[girl] = boy
                    return True

                if dfs(girl_match[girl], visited):
                    girl_match[girl] = boy
                    return True

            return False

        matches = 0

        for boy in range(m):
            visited = [False] * n

            if dfs(boy, visited):
                matches += 1

        return matches

The implementation follows the exact augmenting path strategy described earlier.

The girl_match array stores the current owner of each girl. Initially every entry is -1, meaning no assignments exist.

The DFS function attempts to find a valid girl for the current boy. It iterates through every possible girl and checks whether:

  • The boy can invite her
  • She has not already been explored during the current DFS traversal

The visited array is extremely important. Without it, the DFS could revisit the same girl repeatedly and create infinite recursion cycles.

If a girl is free, the current boy immediately claims her.

If she is already matched, the algorithm recursively attempts to relocate her current partner to another available girl. If that succeeds, the current boy takes her place.

The outer loop processes every boy independently. Each successful DFS increases the matching size by one.

Go Solution

func maximumInvitations(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	girlMatch := make([]int, n)

	for i := 0; i < n; i++ {
		girlMatch[i] = -1
	}

	var dfs func(int, []bool) bool

	dfs = func(boy int, visited []bool) bool {
		for girl := 0; girl < n; girl++ {
			if grid[boy][girl] == 0 || visited[girl] {
				continue
			}

			visited[girl] = true

			if girlMatch[girl] == -1 {
				girlMatch[girl] = boy
				return true
			}

			if dfs(girlMatch[girl], visited) {
				girlMatch[girl] = boy
				return true
			}
		}

		return false
	}

	matches := 0

	for boy := 0; boy < m; boy++ {
		visited := make([]bool, n)

		if dfs(boy, visited) {
			matches++
		}
	}

	return matches
}

The Go implementation closely mirrors the Python solution.

The primary difference is explicit slice allocation and initialization. Since Go arrays default to 0, we must manually initialize girlMatch with -1 to represent unmatched girls.

The DFS is implemented as a recursive closure. Go handles recursion safely for these constraints because the recursion depth is bounded by the number of boys, which is at most 200.

No integer overflow concerns exist because all values remain very small.

Worked Examples

Example 1

grid =
[
  [1,1,1],
  [1,0,1],
  [0,0,1]
]

Initial State

Girl Matched Boy
0 -1
1 -1
2 -1

Process Boy 0

Boy 0 tries girl 0.

Girl 0 is free.

Assign:

Girl Matched Boy
0 0
1 -1
2 -1

Matches = 1

Process Boy 1

Boy 1 tries girl 0.

Girl 0 is already matched with boy 0.

Attempt reassignment:

  • Boy 0 tries girl 1
  • Girl 1 is free

Reassign:

Girl Matched Boy
0 1
1 0
2 -1

Matches = 2

Process Boy 2

Boy 2 can only invite girl 2.

Girl 2 is free.

Assign:

Girl Matched Boy
0 1
1 0
2 2

Matches = 3

Final answer: 3

Example 2

grid =
[
  [1,0,1,0],
  [1,0,0,0],
  [0,0,1,0],
  [1,1,1,0]
]

Process Boy 0

Boy 0 matches with girl 0.

Girl Matched Boy
0 0
1 -1
2 -1
3 -1

Process Boy 1

Boy 1 wants girl 0.

Girl 0 belongs to boy 0.

Attempt reassignment:

  • Boy 0 tries girl 2
  • Girl 2 is free

Reassign:

Girl Matched Boy
0 1
1 -1
2 0
3 -1

Matches = 2

Process Boy 2

Boy 2 wants girl 2.

Girl 2 belongs to boy 0.

Boy 0 cannot move elsewhere.

DFS fails.

Matches remain 2.

Process Boy 3

Boy 3 tries girl 0.

Occupied.

Try reassignment, fails.

Boy 3 then tries girl 1.

Girl 1 is free.

Assign:

Girl Matched Boy
0 1
1 3
2 0
3 -1

Matches = 3

Final answer: 3

Complexity Analysis

Measure Complexity Explanation
Time O(m × n × m) Each DFS may scan all girls and recursively revisit boys
Space O(n) Matching array and visited array

The DFS-based bipartite matching algorithm processes each boy once. During each DFS call, we may potentially examine every girl and recursively trigger additional DFS calls for previously matched boys.

In the worst case, this leads to approximately O(m × n × m) complexity, which is efficient enough for m, n <= 200.

The space usage is modest because we only store:

  • The current matching array
  • The visited array during DFS recursion

Test Cases

from typing import List

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

        girl_match = [-1] * n

        def dfs(boy: int, visited: List[bool]) -> bool:
            for girl in range(n):
                if grid[boy][girl] == 0 or visited[girl]:
                    continue

                visited[girl] = True

                if girl_match[girl] == -1:
                    girl_match[girl] = boy
                    return True

                if dfs(girl_match[girl], visited):
                    girl_match[girl] = boy
                    return True

            return False

        matches = 0

        for boy in range(m):
            visited = [False] * n

            if dfs(boy, visited):
                matches += 1

        return matches

sol = Solution()

assert sol.maximumInvitations([
    [1,1,1],
    [1,0,1],
    [0,0,1]
]) == 3  # Provided example 1

assert sol.maximumInvitations([
    [1,0,1,0],
    [1,0,0,0],
    [0,0,1,0],
    [1,1,1,0]
]) == 3  # Provided example 2

assert sol.maximumInvitations([
    [0]
]) == 0  # Single impossible invitation

assert sol.maximumInvitations([
    [1]
]) == 1  # Single successful invitation

assert sol.maximumInvitations([
    [1,1],
    [1,1]
]) == 2  # Fully connected bipartite graph

assert sol.maximumInvitations([
    [1,0],
    [0,1]
]) == 2  # Independent perfect matching

assert sol.maximumInvitations([
    [1,0],
    [1,0]
]) == 1  # Multiple boys competing for one girl

assert sol.maximumInvitations([
    [0,0,0],
    [0,0,0]
]) == 0  # No edges at all

assert sol.maximumInvitations([
    [1,1,1,1]
]) == 1  # One boy, many girls

assert sol.maximumInvitations([
    [1],
    [1],
    [1]
]) == 1  # Many boys, one girl

assert sol.maximumInvitations([
    [1,1,0],
    [0,1,1],
    [1,0,1]
]) == 3  # Requires augmenting path reassignment

Test Summary

Test Why
Example 1 Validates standard matching behavior
Example 2 Validates reassignment via augmenting paths
[[0]] Smallest impossible case
[[1]] Smallest successful case
Fully connected 2x2 Ensures perfect matching works
Diagonal matching Ensures straightforward assignments
Multiple boys, one girl Tests conflict handling
All zeros Ensures no false matches occur
One boy, many girls Tests asymmetrical dimensions
Many boys, one girl Tests matching capacity limits
Reassignment-heavy graph Validates recursive DFS logic

Edge Cases

One important edge case occurs when the matrix contains only zeros. In this scenario, no boy can invite any girl. A buggy implementation might accidentally increment the match count or mishandle empty DFS traversals. This implementation correctly returns 0 because every DFS immediately fails without finding a valid edge.

Another important case is when many boys compete for the same girl. For example:

[
  [1],
  [1],
  [1]
]

Only one boy can ultimately match with the single available girl. The algorithm handles this naturally because once the girl is assigned, later DFS calls cannot find an augmenting path.

A particularly tricky edge case involves situations where greedy matching fails unless reassignment occurs. Consider:

[
  [1,1],
  [1,0]
]

If boy 0 greedily takes girl 0, boy 1 becomes blocked. However, if boy 0 is reassigned to girl 1, both boys can be matched. The augmenting path DFS correctly discovers this reassignment and produces the optimal result.

Another subtle case is a fully connected graph. In such cases, there are many possible valid matchings. The algorithm does not care which matching it finds, only that the total size is maximum. The augmenting path property guarantees optimality regardless of assignment order.