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> mates(n, -1);  // mates[i] := the i-th girl's mate

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

    return ans;
  }

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