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.

Description Hints 3 Solution Video 9:23

1820. Maximum Number of Accepted Invitations

Medium52.4% acceptance2 companiesPremium elsewhere, free here

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 i^th boy can invite the j^th 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 1^st boy invites the 2^nd girl.
- The 2^nd boy invites the 1^st girl.
- The 3^rd boy invites the 3^rd 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 1^st boy invites the 3^rd girl.
-The 2^nd boy invites the 1^st girl.
-The 3^rd boy invites no one.
-The 4^th boy invites the 2^nd girl.

Constraints:

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

Asked at 2 companies

Bloomberg

Google

Topics

Hints open one at a time

Hint 1

We can see that the problem can be represented as a directed graph with an edge from each boy to the girl he invited.

Hint 2

We need to choose a set of edges such that no to source points in the graph (i.e., boys) have an edge with the same endpoint (i.e., the same girl).

Hint 3

The problem is maximum bipartite matching in the graph.

9:23

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

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

Your code is saved on this device.Solution