# 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 mates(n, -1); // mates[i] := the i-th girl's mate for (int i = 0; i < m; ++i) if (canInvite(grid, i, vector(n), mates)) ++ans; return ans; } private: // Returns true if the i-th boy can make an invitation. bool canInvite(const vector>& grid, int i, vector&& seen, vector& mates) { // The i-th boy asks each girl. for (int j = 0; j < seen.size(); ++j) { if (!grid[i][j] || seen[j]) continue; seen[j] = true; if (mates[j] == -1 || canInvite(grid, mates[j], move(seen), mates)) { mates[j] = i; // Match the j-th girl with i-th boy. 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[] mates = new int[n]; // mates[i] := the i-th girl's mate Arrays.fill(mates, -1); for (int i = 0; i < m; ++i) if (canInvite(grid, i, new boolean[n], mates)) ++ans; return ans; } // Returns true if the i-th boy can make an invitation. private boolean canInvite(int[][] grid, int i, boolean[] seen, int[] mates) { // The i-th boy asks each girl. for (int j = 0; j < seen.length; ++j) { if (grid[i][j] == 0 || seen[j]) continue; seen[j] = true; if (mates[j] == -1 || canInvite(grid, mates[j], seen, mates)) { mates[j] = i; // Match the j-th girl with i-th boy. 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 class Solution: def maximumInvitations(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) ans = 0 mates = [-1] * n # mates[i] := the i-th girl's mate def canInvite(i: int, seen: List[bool]) -> bool: """Returns True if the i-th boy can make an invitation.""" # The i-th boy asks each girl. for j in range(n): if not grid[i][j] or seen[j]: continue seen[j] = True if mates[j] == -1 or canInvite(mates[j], seen): mates[j] = i # Match the j-th girl with i-th boy. return True return False for i in range(m): seen = [False] * n if canInvite(i, seen): ans += 1 return ans