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.

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;
    }
}

All Problems

All Solutions