How hard is LeetCode 1820. Maximum Number of Accepted Invitations?

LeetCode 1820. Maximum Number of Accepted Invitations is rated Medium on LeetCode.

What is the time complexity of LeetCode 1820. Maximum Number of Accepted Invitations?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 1820. Maximum Number of Accepted Invitations?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 1820. Maximum Number of Accepted Invitations cover?

LeetCode 1820. Maximum Number of Accepted Invitations is tagged Depth-First Search, Graph, Array and Matrix on LeetCode.

Is LeetCode 1820. Maximum Number of Accepted Invitations a premium problem?

Yes. LeetCode 1820. Maximum Number of Accepted Invitations is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Maximum Number of Accepted Invitations — LeetCode 1820 Python Solution

MediumLeetCode PremiumDepth-First SearchGraphArrayMatrix

Problem: #1820
Pattern: Matrix and Grid
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: grid = [[1,1,1],
Output: 3
Explanation: The invitations are sent as follows:

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(V) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1820. Maximum Number of Accepted Invitations is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1820. Maximum Number of Accepted Invitations?: LeetCode 1820. Maximum Number of Accepted Invitations is rated Medium on LeetCode.
What is the time complexity of LeetCode 1820. Maximum Number of Accepted Invitations?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 1820. Maximum Number of Accepted Invitations?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 1820. Maximum Number of Accepted Invitations cover?: LeetCode 1820. Maximum Number of Accepted Invitations is tagged Depth-First Search, Graph, Array and Matrix on LeetCode.
Is LeetCode 1820. Maximum Number of Accepted Invitations a premium problem?: Yes. LeetCode 1820. Maximum Number of Accepted Invitations is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.