# 1820. Maximum Number of Accepted Invitations

• Time: $O((m + n)^3)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: int maximumInvitations(vector>& grid) { const int m = grid.size(); const int n = grid[0].size(); int ans = 0; vector mate(n, -1); // girl's mate for (int i = 0; i < m; ++i) if (canInvite(grid, i, vector(n), mate)) ++ans; return ans; } private: // Returns true if boy i can make an invitation. bool canInvite(const vector>& grid, int i, vector&& seen, vector& mate) { // Boy i ask each girl. for (int j = 0; j < seen.size(); ++j) { if (!grid[i][j] || seen[j]) continue; seen[j] = true; if (mate[j] == -1 || canInvite(grid, mate[j], move(seen), mate)) { mate[j] = i; // Match girl j w/ boy i. return true; } } return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public int maximumInvitations(int[][] grid) { final int m = grid.length; final int n = grid[0].length; int ans = 0; int[] mate = new int[n]; // girl's mate Arrays.fill(mate, -1); for (int i = 0; i < m; ++i) if (canInvite(grid, i, new boolean[n], mate)) ++ans; return ans; } // Returns true if boy i can make an invitation. private boolean canInvite(int[][] grid, int i, boolean[] seen, int[] mate) { // Boy i ask each girl. for (int j = 0; j < seen.length; ++j) { if (grid[i][j] == 0 || seen[j]) continue; seen[j] = true; if (mate[j] == -1 || canInvite(grid, mate[j], seen, mate)) { mate[j] = i; // Match girl j w/ boy i. return true; } } return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def maximumInvitations(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) ans = 0 mate = [-1] * n # girl's mate # Returns true if boy i can make an invitation. def canInvite(i, seen): for j in range(n): if not grid[i][j] or seen[j]: continue seen[j] = True if mate[j] == -1 or canInvite(mate[j], seen): mate[j] = i # Match girl j with boy i return True return False for i in range(m): seen = [False] * n if canInvite(i, seen): ans += 1 return ans