Skip to content

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<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;
    vector<int> mate(n, -1);  // girl's mate

    for (int i = 0; i < m; ++i)
      if (canInvite(grid, i, vector<bool>(n), mate))
        ++ans;

    return ans;
  }

 private:
  // Returns true if boy i can make an invitation.
  bool canInvite(const vector<vector<int>>& grid, int i, vector<bool>&& seen,
                 vector<int>& 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