We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Accepted Invitations

Number: 1969

Difficulty: Medium

Paid? Yes

Companies: Google, Uber, Bloomberg

Problem Description

Given an m x n grid where grid[i][j] is either 0 or 1, each row representing a boy and each column representing a girl; a 1 indicates that the boy i can invite girl j. Each boy can invite at most one girl and each girl can accept at most one invitation. Return the maximum number of accepted invitations.

Key Insights

  • The problem can be modeled as a bipartite graph matching problem where boys and girls are two disjoint sets.
  • An edge exists between boy i and girl j if grid[i][j] == 1.
  • The goal is to find the maximum number of pairings (matches) such that no boy or girl appears in more than one pairing.
  • DFS-based augmenting path search (or alternatively, the Hungarian algorithm) works efficiently given the grid constraints (m, n ≤ 200).

Space and Time Complexity

Time Complexity: O(m * n) in the worst-case scenario using DFS for finding augmenting paths. Space Complexity: O(m + n) for maintaining matching arrays and the recursion stack.

Solution

We solve the problem by transforming it into a bipartite matching problem. Boys form one set and girls form the other. For each boy, we try to find an unmatched girl he can invite by performing a DFS that searches for an augmenting path. If a girl is already matched, we recursively attempt to find another match for her current partner. This process continues until no further augmenting path can be found, maximizing the accepted invitations.

The algorithm uses a DFS helper function to try and perform a valid matching for each boy. Upon a successful DFS execution, which finds a girl (either unmatched or through reassigning a current match), the matching count is increased. This DFS approach is both straightforward and efficient for the problem constraints.

Code Solutions

# Python solution for Maximum Number of Accepted Invitations

def maximumInvitations(grid):
    # number of boys and girls
    m = len(grid)
    n = len(grid[0])
    
    # match[j] will be the index of boy matched with girl j, or -1 if girl j is unmatched
    match = [-1] * n

    # DFS function to try to match boy 'i' with a girl.
    def dfs(i, seen):
        for j in range(n):
            # If boy i can invite girl j and j hasn't been visited
            if grid[i][j] == 1 and not seen[j]:
                seen[j] = True
                # if girl j is unmatched or we can reassign the boy currently matched with j
                if match[j] == -1 or dfs(match[j], seen):
                    match[j] = i
                    return True
        return False

    result = 0
    for i in range(m):
        # seen array keeps track of visited girls for the current boy in DFS
        seen = [False] * n
        if dfs(i, seen):
            result += 1
    return result

# Example usage:
grid1 = [[1,1,1],
         [1,0,1],
         [0,0,1]]
print(maximumInvitations(grid1))  # Output: 3
← Back to All Questions