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<sup>th</sup> boy can invite the j<sup>th</sup> 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.

Let’s solve the "Maximum Accepted Invitations" problem in your structured interview format – clear, optimal, and scalable.

✅ 1. Problem Explanation (In Simple Terms)

You have:

m boys
n girls
A grid where grid[i][j] == 1 means boy i can invite girl j

Rules:

Each boy can invite at most one girl
Each girl can accept at most one invitation
A match happens only if both conditions are satisfied

🔍 Your goal: maximize the number of accepted invitations.

💡 2. Key Insights

This is a maximum bipartite matching problem:
- Boys = nodes on left
- Girls = nodes on right
- grid[i][j] == 1 = edge between boy i and girl j
You're trying to find the maximum number of pairings (matchings) such that:
- No boy is matched more than once
- No girl is matched more than once
Can be solved using DFS-based matching (a greedy approach similar to the Hungarian algorithm but simplified)

🧠 3. Steps to Solve

Initialize an array matchToGirl[j] = i to track which boy is matched to girl j
For each boy i:
- Try to find a girl he can invite via DFS
- Use a visited set to avoid cycles in DFS
- If a girl is free, match directly
- If not, recursively try to rematch her current boy
Count all successful matches

✅ 4. JavaScript Code (Optimized & Well-Commented)

/**
 * @param {number[][]} grid
 * @return {number}
 */
function maxNumberOfAcceptedInvitations(grid) {
  const m = grid.length;       // boys
  const n = grid[0].length;    // girls
  const matchToBoy = Array(n).fill(-1); // girl j matched to which boy (or -1 if unmatched)

  // DFS to try matching boy i
  function canMatch(boy, visited) {
    for (let girl = 0; girl < n; girl++) {
      if (grid[boy][girl] === 1 && !visited[girl]) {
        visited[girl] = true;

        // If girl is unmatched or her matched boy can be reassigned
        if (matchToBoy[girl] === -1 || canMatch(matchToBoy[girl], visited)) {
          matchToBoy[girl] = boy;
          return true;
        }
      }
    }
    return false;
  }

  let result = 0;
  for (let boy = 0; boy < m; boy++) {
    const visited = Array(n).fill(false);
    if (canMatch(boy, visited)) {
      result++;
    }
  }

  return result;
}

🔍 5. Dry Run Example

Input:
grid = [
  [1, 1, 1],
  [1, 0, 1],
  [0, 0, 1]
]

Matching:

Boy 0 → Girl 1
Boy 1 → Girl 0
Boy 2 → Girl 2

✅ Output: 3 matchings possible

⏱️ 6. Time & Space Complexity

Let:

m = number of boys
n = number of girls

Time Complexity:

Each boy tries to find a match: O(m)
For each girl, we do DFS across up to n girls: O(n)
Total worst case: O(m * n)

✅ Time: O(m * n)
✅ Space: O(n) for match + visited array

✅ Final Verdict

Elegant and efficient solution using DFS-based bipartite matching
Works well for sparse or dense grids
Scales to m, n ≤ 1000 easily with some tweaks

Let me know if you want:

A visual match pairing
The actual matching pairs
Or the BFS-based version (Hopcroft-Karp) for even faster matching in large graphs

Maximum Number of Accepted Invitations