Skip to main content
Talentd

Maximum Number of Accepted Invitations - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDepth-First SearchGraphMatrix6 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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 most one girl, and a girl can accept at most one invitation from a boy.

Return the maximum possible number of accepted invitations.

 

Example 1:

Input: grid = [[1,1,1],
               [1,0,1],
               [0,0,1]]
Output: 3
Explanation: 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:

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.

Approach Overview

Problem Overview: You are given a binary matrix where rows represent boys and columns represent girls. A value of 1 means the boy can invite that girl. Each girl can accept at most one invitation, and each boy can send at most one accepted invitation. The goal is to maximize the total number of accepted invitations.

Approach 1: Backtracking / Brute Force (Exponential Time)

The most direct way is to try every possible assignment between boys and girls. For each boy, iterate through all girls he can invite and attempt to match them if the girl is currently unassigned. If a girl is already matched, backtrack and try a different pairing. This explores every valid combination of matches and keeps track of the maximum count found.

This method models the problem as a matching search but without optimization. Because every boy–girl pairing may branch into multiple possibilities, the complexity grows exponentially with the number of nodes. Time complexity is roughly O(2^(m*n)) in the worst case, with O(m+n) auxiliary space for tracking assignments. This approach is mainly useful for understanding the matching constraints but is not practical for real input sizes.

Approach 2: Hungarian Algorithm / DFS Augmenting Path (O(m * n^2))

The matrix naturally forms a bipartite graph: boys on the left, girls on the right. Each grid[i][j] == 1 represents an edge between boy i and girl j. The problem becomes finding the maximum bipartite matching. The Hungarian-style DFS matching approach builds the matching incrementally.

For every boy, run a DFS to try assigning a girl. If a girl is free, match them immediately. If the girl is already matched with another boy, attempt to reassign that boy to a different compatible girl using another DFS. This process searches for an augmenting path that increases the total number of matches. A visited array prevents cycles during each DFS attempt.

The key insight is that re-routing existing matches can unlock better global pairings. Each boy triggers a DFS that may traverse multiple edges, but each attempt remains bounded by the number of girls. The overall time complexity is O(m * n^2) and space complexity is O(n) for storing matches and visited states.

This technique is a classic application of graph algorithms combined with depth-first search on a bipartite structure derived from a matrix. It scales efficiently for typical constraints and is widely used for assignment problems.

Recommended for interviews: Interviewers expect the bipartite matching perspective. Showing the brute force idea demonstrates understanding of the constraints, but implementing the DFS-based Hungarian algorithm shows strong graph modeling skills and familiarity with augmenting path techniques.

Solution

This problem belongs to the maximum matching problem of bipartite graphs, which is suitable for solving with the Hungarian algorithm.

The core idea of the Hungarian algorithm is to continuously start from unmatched points, look for augmenting paths, and stop when there are no augmenting paths. This gives the maximum match.

The time complexity is O(m times n).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking / Brute ForceO(2^(m*n))O(m+n)Conceptual understanding of assignment possibilities or very small inputs
Hungarian Algorithm (DFS Augmenting Path)O(m * n^2)O(n)General solution for bipartite matching problems and typical interview expectations

Video Solution

LeetCode 1820. Maximum Number of Accepted Invitations | maximum bipartite matching | Locked Question • 宰相小甘罗 • 3,978 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Maximum Number of Accepted Invitations easy or hard?
The problem is rated Medium because the implementation is straightforward once you recognize it as a bipartite matching problem. The main challenge is identifying the graph model and understanding augmenting paths. Developers familiar with DFS and matching algorithms usually solve it quickly.
Maximum Number of Accepted Invitations Python/Java solution
Most implementations follow the DFS-based Hungarian algorithm. Maintain an array that records which boy is currently matched with each girl. For each boy, run a DFS that tries to match with an available girl or reassign the girl's existing match. This approach works consistently in Python, Java, C++, and Go.
How to solve Maximum Number of Accepted Invitations in O(n)?
An O(n) solution is not possible because the algorithm must examine potential edges between boys and girls. The optimal practical solution is the Hungarian-style DFS matching algorithm with O(m * n^2) complexity. It efficiently finds augmenting paths to maximize matches in the bipartite graph.
What is the best approach for Maximum Number of Accepted Invitations?
The most effective approach is modeling the grid as a bipartite graph and applying the Hungarian algorithm using DFS to find augmenting paths. Each boy attempts to match with a girl, and if that girl is already matched, the algorithm tries to reassign the previous match. This method guarantees the maximum bipartite matching with O(m * n^2) time complexity.
Is Maximum Number of Accepted Invitations asked at Google/Amazon/Meta?
This problem represents a classic bipartite matching pattern that frequently appears in interviews at companies like Google, Amazon, and Meta. Variants often involve assigning workers to jobs, students to projects, or matching resources under constraints. Recognizing the graph matching structure is the key interview skill.
What data structure is used in Maximum Number of Accepted Invitations?
The problem primarily uses graph data structures derived from the input matrix. The matrix represents adjacency between two partitions of nodes, and arrays track the current matching for each girl. Depth-first search is used to explore augmenting paths during matching.
What is the time complexity of Maximum Number of Accepted Invitations?
The DFS-based Hungarian algorithm runs in O(m * n^2) time where m is the number of boys and n is the number of girls. Each boy triggers a DFS that may traverse multiple edges while attempting to reassign matches. Space complexity is O(n) for storing the current matching and visited states.

Ready to solve this problem?

Practice Maximum Number of Accepted Invitations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays