Maximum Good People Based on Statements

Hard

Asked by:

12 views

Topics:

ArraysBit Manipulation

There are two types of persons:

The good person: The person who always tells the truth.
The bad person: The person who might tell the truth and might lie.

You are given a 0-indexed 2D integer array statements of size n x n that represents the statements made by n people about each other. More specifically, statements[i][j] could be one of the following:

0 which represents a statement made by person i that person j is a bad person.
1 which represents a statement made by person i that person j is a good person.
2 represents that no statement is made by person i about person j.

Additionally, no person ever makes a statement about themselves. Formally, we have that statements[i][i] = 2 for all 0 <= i < n.

Return the maximum number of people who can be good based on the statements made by the n people.

Example 1:

Input: statements = [[2,1,2],[1,2,2],[2,0,2]]
Output: 2
Explanation: Each person makes a single statement.
- Person 0 states that person 1 is good.
- Person 1 states that person 0 is good.
- Person 2 states that person 1 is bad.
Let's take person 2 as the key.
- Assuming that person 2 is a good person:
- Based on the statement made by person 2, person 1 is a bad person.
- Now we know for sure that person 1 is bad and person 2 is good.
- Based on the statement made by person 1, and since person 1 is bad, they could be:
- telling the truth. There will be a contradiction in this case and this assumption is invalid.
- lying. In this case, person 0 is also a bad person and lied in their statement.
- Following that person 2 is a good person, there will be only one good person in the group.
- Assuming that person 2 is a bad person:
- Based on the statement made by person 2, and since person 2 is bad, they could be:
- telling the truth. Following this scenario, person 0 and 1 are both bad as explained before.
- Following that person 2 is bad but told the truth, there will be no good persons in the group.
- lying. In this case person 1 is a good person.
- Since person 1 is a good person, person 0 is also a good person.
- Following that person 2 is bad and lied, there will be two good persons in the group.
We can see that at most 2 persons are good in the best case, so we return 2.
Note that there is more than one way to arrive at this conclusion.

Example 2:

Input: statements = [[2,0],[0,2]]
Output: 1
Explanation: Each person makes a single statement.
- Person 0 states that person 1 is bad.
- Person 1 states that person 0 is bad.
Let's take person 0 as the key.
- Assuming that person 0 is a good person:
    - Based on the statement made by person 0, person 1 is a bad person and was lying.
    - Following that person 0 is a good person, there will be only one good person in the group.
- Assuming that person 0 is a bad person:
    - Based on the statement made by person 0, and since person 0 is bad, they could be:
        - telling the truth. Following this scenario, person 0 and 1 are both bad.
            - Following that person 0 is bad but told the truth, there will be no good persons in the group.
        - lying. In this case person 1 is a good person.
            - Following that person 0 is bad and lied, there will be only one good person in the group.
We can see that at most, one person is good in the best case, so we return 1.
Note that there is more than one way to arrive at this conclusion.

Constraints:

n == statements.length == statements[i].length
2 <= n <= 15
statements[i][j] is either 0, 1, or 2.
statements[i][i] == 2

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `statements` array (i.e., the maximum value of n)?
For `statements[i][j]`, can the value ever be something other than 0, 1, or 2?
If no consistent group can be formed (e.g., due to contradictory statements), what value should I return?
Is there a guaranteed minimum size for the input array `statements`? For example, will it ever be null or empty?
To confirm my understanding, a 'consistent group' means that if person 'i' is good, then `statements[i][j]` must accurately reflect person 'j' (either 1 if 'j' is good or 0 if 'j' is a liar). Similarly, if person 'i' is a liar, then statements made by person 'i' cannot accurately reflect person 'j', i.e., 'i' claims 'j' is good and 'j' is actually a liar, or 'i' claims 'j' is a liar and 'j' is actually good. Is that correct?

Brute Force Solution

Approach

The brute force strategy for this problem means trying every possible combination of who could be a good person and who could be a bad person. We then check if each of those combinations is consistent with the statements given to us.

Here's how the algorithm would work step-by-step:

First, imagine every person could be good or bad - that's our starting point. We're going to try every single possibility.
For example, let's say we have 3 people. One possibility is all three are good. Another is the first is good, the second is bad, and the third is good, and so on. We need to consider all combinations.
For each of these possibilities, we need to check if it makes sense with what each person said.
To check, we go through each person and look at their statement. If that person is supposedly 'good', then their statement must be true, given the current assumption of who's good and bad.
If the person is supposedly 'bad', then their statement must be false, given the current assumption of who's good and bad.
If any person's statement doesn't match their supposed 'good' or 'bad' status, then that whole possibility is thrown out because it's inconsistent.
If we get through every person and all their statements are consistent with who's good and who's bad, then we count how many 'good' people are in that possibility.
After checking every possible combination of good and bad people, we pick the scenario with the most 'good' people in it. That's our answer.

Code Implementation

def maximum_good_people_brute_force(statements):
    number_of_people = len(statements)
    maximum_good_people = 0

    for i in range(2 ** number_of_people):
        # Create a possible assignment of good/bad people based on the bitmask
        people_assignments = []
        for j in range(number_of_people):
            if (i >> j) & 1:
                people_assignments.append(1)
            else:
                people_assignments.append(0)

        is_consistent = True

        # Check if the statements are consistent with the assignments
        for person_index in range(number_of_people):
            if people_assignments[person_index] == 1:
                for target_index in range(number_of_people):
                    statement = statements[person_index][target_index]
                    if statement == 2:
                        continue

                    # Validate the statement against the assignment
                    if statement != people_assignments[target_index]:
                        is_consistent = False
                        break
            if not is_consistent:
                break

        # If statements are consistent, count number of good people
        if is_consistent:

            # Count how many people are labeled as good in this assignment
            current_good_people = sum(people_assignments)

            # Keep track of the maximum number of good people seen so far
            maximum_good_people = max(maximum_good_people, current_good_people)

    return maximum_good_people

Big(O) Analysis

Time Complexity

O(n * 2^n) – The algorithm iterates through all possible combinations of good and bad people. With n people, there are 2^n such combinations. For each combination, the algorithm iterates through each person (n), and for each person, it might iterate through their statements which, in the worst case, could involve checking the status of every other person. So, in the worst case, checking consistency for each combination takes O(n * n) time (as each person can potentially make statements about all n people). Thus, the overall time complexity is dominated by trying all 2^n combinations, where each combination takes at most O(n * n) to verify. Therefore the overall time complexity is O(n * n * 2^n) but can be simplified to O(n * 2^n), as the n^2 verification is being multiplied by 2^n.

Space Complexity

O(1) – The described brute force algorithm primarily iterates through possible combinations of good and bad people and checks their consistency. The plain English explanation doesn't mention the use of any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or visited states. Only a few variables are required to keep track of the current combination being tested and the maximum number of good people found so far. Therefore, the space complexity remains constant, independent of the number of people (N).

Optimal Solution

Approach

The core idea is to explore possible scenarios by assuming different people are good or bad and checking if those assumptions are consistent with all the statements. We aim to find the largest group of good people that doesn't lead to contradictions in the provided statements.

Here's how the algorithm would work step-by-step:

Think of each person as either being 'good' or 'bad'. Since we don't know who is who, we need to explore different combinations.
Start by guessing a specific combination of good and bad people. For example, maybe everyone is bad, or maybe only the first person is good.
With your current guess, check if the statements made by the 'good' people in your guess are actually true based on who you've labeled as 'good' and 'bad'. Also, check if the statements made by the 'bad' people are false.
If any statement contradicts your guess about who's good and bad, then that guess is wrong. Discard it and try a different one.
Keep track of the largest group of 'good' people you've found so far that doesn't create any contradictions.
Continue exploring different combinations until you've considered all possible groups of 'good' and 'bad' people.
Return the size of the largest consistent group of 'good' people you found. That's the maximum number of people who could be telling the truth.

Code Implementation

def maximum_good_people(statements):
    number_of_people = len(statements)
    maximum_good = 0

    # Iterate through all possible scenarios of good/bad people.
    for i in range(2 ** number_of_people):
        good_count = 0
        is_valid = True
        people_types = []

        for person_index in range(number_of_people):
            if (i >> person_index) & 1:
                people_types.append(1) # 1 represents good
                good_count += 1
            else:
                people_types.append(0) # 0 represents bad

        # Check if the current scenario is valid
        for person_index in range(number_of_people):
            statement_index = 0
            for statement in statements[person_index]:
                #If the person is good, their statement must be true.
                if people_types[person_index] == 1:
                    if statement != 2:
                        if (statement != people_types[statement_index]):
                            is_valid = False
                            break

                #If the person is bad, check if their statement causes contradiction.
                else:
                    if statement != 2:
                        pass

                statement_index += 1
            if not is_valid:
                break

        if is_valid:
            #Update the maximum number of good people found.
            maximum_good = max(maximum_good, good_count)

    return maximum_good

Big(O) Analysis

Time Complexity

O(n * 2^n) – The algorithm explores all possible combinations of good and bad people. Since there are n people, there are 2^n possible combinations to consider. For each of these 2^n combinations, the algorithm iterates through all n people to check the consistency of their statements. Therefore, the overall time complexity is approximately n * 2^n, where n is the number of people.

Space Complexity

O(1) – The algorithm explores different combinations of good and bad people without explicitly storing all combinations. It keeps track of the largest consistent group size found so far using a single integer variable. Therefore, the auxiliary space used remains constant regardless of the input size N (number of people), leading to a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty `statements` array	Return 0 since there are no people and thus no consistent group.
Single person scenario (n=1)	The person can always be good, so return 1.
All statements are 'unknown' (all values are 2)	All people can be good, so return n.
No consistent group exists (conflicting statements)	The algorithm should explore all possibilities and return 0 if none are consistent.
Maximum number of people (n is large, near limit)	The algorithm should have a time complexity that makes this manageable, potentially exponential but optimized.
Statements are highly biased (mostly 0s or mostly 1s)	The algorithm should handle unbalanced distributions of statements without being significantly affected.
Integer overflow if calculating number of 'good' people using multiplication.	The code must use appropriate data types and techniques (e.g., bit manipulation) to avoid integer overflow.
Algorithm's recursion depth exceeds limits for large n.	The solution should use iteration or memoization/dynamic programming to avoid excessive recursion depth.

Null or empty `statements` array

How to Handle:

Return 0 since there are no people and thus no consistent group.

Single person scenario (n=1)

How to Handle:

The person can always be good, so return 1.

All statements are 'unknown' (all values are 2)

How to Handle:

All people can be good, so return n.

No consistent group exists (conflicting statements)

How to Handle:

The algorithm should explore all possibilities and return 0 if none are consistent.

Maximum number of people (n is large, near limit)

How to Handle:

The algorithm should have a time complexity that makes this manageable, potentially exponential but optimized.

Statements are highly biased (mostly 0s or mostly 1s)

How to Handle:

The algorithm should handle unbalanced distributions of statements without being significantly affected.

Integer overflow if calculating number of 'good' people using multiplication.

How to Handle:

The code must use appropriate data types and techniques (e.g., bit manipulation) to avoid integer overflow.

Algorithm's recursion depth exceeds limits for large n.

How to Handle:

The solution should use iteration or memoization/dynamic programming to avoid excessive recursion depth.