Maximum Number of Accepted Invitations

Maximum Number of Accepted Invitations

What is this problem about?

The Maximum Number of Accepted Invitations coding problem models a bipartite matching scenario: you have m boys and n girls, and a grid indicates which boy-girl pairs are compatible. Each boy can invite at most one girl, and each girl can accept at most one invitation. Maximize the total number of accepted invitations. This is the classic maximum bipartite matching problem.

Why is this asked in interviews?

Uber, Google, and Bloomberg include this problem because maximum bipartite matching is a fundamental graph algorithm. It tests knowledge of augmenting paths via DFS (the standard matching algorithm used in interviews). While advanced algorithms like Hopcroft-Karp exist, the simpler augmenting path DFS is the expected approach here, and it runs in O(m * n) for dense bipartite graphs.

Algorithmic pattern used

Augmenting path DFS (Hungarian-style matching): For each boy, try to find an augmenting path — a path from this boy through alternating unmatched/matched edges to a free girl. Maintain a match array tracking which boy each girl is currently matched to. For each unmatched boy, run DFS: try each compatible girl; if she's free, match them; if she's matched to another boy, recursively try to re-route that boy. The total matches found is the answer.

Time: O(m * n) per augmenting path × m boys = O(m² * n) worst case, acceptable for typical constraints.

Example explanation

Boys: 2, Girls: 3. Grid: [[1,1,0],[0,1,1]]

• Boy 0 can invite Girl 0 or 1. Boy 1 can invite Girl 1 or 2.
• Try Boy 0 → Girl 0. Free! Match(0,0). Count=1.
• Try Boy 1 → Girl 1. Free! Match(1,1). Count=2.
• Answer = 2.

If grid were [[1,1,0],[1,0,0]]:

• Boy 0 → Girl 0. Match(0,0). Count=1.
• Boy 1 → Girl 0 (only option). Girl 0 matched to Boy 0. Try to re-route Boy 0 to Girl 1. Girl 1 free! Re-route. Match(0,1), Match(1,0). Count=2.
• Augmenting path found: 2 matches.

Common mistakes candidates make

• Not using a visited array in DFS: Without tracking which girls have been tried in the current augmentation attempt, the DFS can cycle infinitely.
• Resetting the visited array per boy, not globally: The visited array must be reset for each new boy's augmentation attempt, not once for the entire algorithm.
• Confusing bipartite matching with general matching: Here, only boy-to-girl edges exist — bipartite structure simplifies the algorithm significantly.

Interview preparation tip

For the Array Matrix Graph Depth-First Search interview pattern, implement the augmenting path matching algorithm cleanly: tryMatch(boy, visited) returns true if an augmenting path exists. Call it for each unmatched boy. The visited array prevents re-checking the same girl in one augmentation. This template solves all bipartite matching problems encountered in interviews.