Problem statement

https://leetcode.com/problems/maximum-number-of-accepted-invitations/

Solution

Actually I am quite suprised to see this problem on leetcode and even more marked as medium, not hard. In this problem we need to find the maximum match in bipartite graph, which is quite classical problem, but if you do not know how to solve it, there is no change you will do it in real interview. The high-level idea is to so-called augmenting paths, on each iteration we try to extend found biggest matching so-far. It can be proved that it is enough to make this only m times.

Complexity

Time complexity is O(E*m), where E <= m*n is number of edges, space complexity is O(n).

Code

class Solution:
    def maximumInvitations(self, grid):
        m, n = len(grid), len(grid[0])
        G = defaultdict(list)
        for x, y in product(range(m), range(n)):
            if grid[x][y] == 1: G[x].append(y)
        
        def dfs(x, flag):
            for i in G[x]:
                if vis[i] == flag: continue
                vis[i] = flag
                if match[i] == -1 or dfs(match[i], flag):
                    match[i] = x
                    return 1
            return 0
        
        vis, match, res = [0]*n, [-1]*n, 0
        
        for i in range(m):
            if dfs(i, i+1):
                res += 1
                
        return res