Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1820.html

1820. Maximum Number of Accepted Invitations

Level

Medium

Description

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

Solution

Use backtrack. For each boy, find a girl that matches the boy, and the number of accepted invitations is added by 1 if such a match is found. Finally, return the maximum number of accepted invitations.

• Java
• C++
• Python
• Go

• class Solution {
      int maxInvitations = 0;
  
      public int maximumInvitations(int[][] grid) {
          int rows = grid.length, columns = grid[0].length;
          int[] matches = new int[columns];
          Arrays.fill(matches, -1);
          for (int i = 0; i < rows; i++) {
              boolean[] visited = new boolean[columns];
              if (backtrack(grid, i, visited, matches))
                  maxInvitations++;
          }
          return maxInvitations;
      }
  
      public boolean backtrack(int[][] grid, int row, boolean[] visited, int[] matches) {
          int columns = visited.length;
          for (int j = 0; j < columns; j++) {
              if (grid[row][j] == 1 && !visited[j]) {
                  visited[j] = true;
                  if (matches[j] == -1 || backtrack(grid, matches[j], visited, matches)) {
                      matches[j] = row;
                      return true;
                  }
              }
          }
          return false;
      }
  }
  
  ############
  
  class Solution {
      private int[][] grid;
      private boolean[] vis;
      private int[] match;
      private int n;
  
      public int maximumInvitations(int[][] grid) {
          int m = grid.length;
          n = grid[0].length;
          this.grid = grid;
          vis = new boolean[n];
          match = new int[n];
          Arrays.fill(match, -1);
          int ans = 0;
          for (int i = 0; i < m; ++i) {
              Arrays.fill(vis, false);
              if (find(i)) {
                  ++ans;
              }
          }
          return ans;
      }
  
      private boolean find(int i) {
          for (int j = 0; j < n; ++j) {
              if (grid[i][j] == 1 && !vis[j]) {
                  vis[j] = true;
                  if (match[j] == -1 || find(match[j])) {
                      match[j] = i;
                      return true;
                  }
              }
          }
          return false;
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-number-of-accepted-invitations/
  // Time: O(?)
  // Space: O(N)
  class Solution {
  public:
      int maximumInvitations(vector<vector<int>>& A) {
          int M = A.size(), N = A[0].size(), ans = 0;
          vector<int> match(N, -1);
          vector<bool> seen;
          function<bool(int)> dfs = [&](int u) {
              for (int v = 0; v < N; ++v) {
                  if (!A[u][v] || seen[v]) continue; // If there is no edge between (u, v), or this girl is visited already, skip
                  seen[v] = true;
                  if (match[v] == -1 || dfs(match[v])) {
                      match[v] = u;
                      return true;
                  }
              }
              return false;
          };
          for (int i = 0; i < M; ++i) { // Try each node as the starting point of DFS
              seen.assign(N, false);
              if (dfs(i)) ++ans;
          }
          return ans;
      }
  };
  

• class Solution:
      def maximumInvitations(self, grid: List[List[int]]) -> int:
          def find(i):
              for j, v in enumerate(grid[i]):
                  if v and j not in vis:
                      vis.add(j)
                      if match[j] == -1 or find(match[j]):
                          match[j] = i
                          return True
              return False
  
          m, n = len(grid), len(grid[0])
          match = [-1] * n
          ans = 0
          for i in range(m):
              vis = set()
              ans += find(i)
          return ans
  
  
  

• func maximumInvitations(grid [][]int) int {
  	m, n := len(grid), len(grid[0])
  	var vis map[int]bool
  	match := make([]int, n)
  	for i := range match {
  		match[i] = -1
  	}
  	var find func(i int) bool
  	find = func(i int) bool {
  		for j, v := range grid[i] {
  			if v == 1 && !vis[j] {
  				vis[j] = true
  				if match[j] == -1 || find(match[j]) {
  					match[j] = i
  					return true
  				}
  			}
  		}
  		return false
  	}
  	ans := 0
  	for i := 0; i < m; i++ {
  		vis = map[int]bool{}
  		if find(i) {
  			ans++
  		}
  	}
  	return ans
  }
  

All Problems

All Solutions