Maximum Number of Accepted Invitations - Solution & Explanation

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.