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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Good People Based on Statements

Difficulty: Hard

Problem Description

You are given a 2D integer array statements that represents statements made by n people about each other. Each statement indicates whether a person believes another person is good (1), bad (0), or if no statement is made (2). Your task is to return the maximum number of people who can be classified as good based on these statements.

Key Insights

  • Each person can either be good (truth-teller) or bad (liar).
  • The statements made by good persons are always true, while bad persons can either tell the truth or lie.
  • The problem can be approached by checking all possible subsets of people to determine if they can be classified as good or bad without contradictions.
  • The constraints (n <= 15) allow for a bitmasking approach to explore all combinations efficiently.

Space and Time Complexity

Time Complexity: O(2^n * n) - This accounts for the 2^n subsets of people and the O(n) time to verify each subset. Space Complexity: O(n) - This space is used for storing the statements and the current subset being evaluated.

Solution

To solve the problem, we will use a bitmasking technique to represent each subset of people. For each subset, we will verify if the assumptions about who is good and who is bad lead to any contradictions based on the statements. If a subset is valid, we will check if its size is the largest found so far.

  1. Iterate through all possible subsets of people using a bitmask.
  2. For each subset, assume the people in it are good and the rest are bad.
  3. Validate the assumptions against the statements provided.
  4. Keep track of the maximum size of valid good people found.

Code Solutions

def maximumGood(statements):
    n = len(statements)
    max_good = 0

    for mask in range(1 << n):
        good_count = 0
        valid = True

        for i in range(n):
            if (mask & (1 << i)) > 0:
                good_count += 1
                for j in range(n):
                    if statements[i][j] == 1 and (mask & (1 << j)) == 0:
                        valid = False
                    if statements[i][j] == 0 and (mask & (1 << j)) > 0:
                        valid = False

        if valid:
            max_good = max(max_good, good_count)

    return max_good
← Back to All Questions