#2151

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Maximum Good People Based on Statements

Determine the maximum number of good people in a group given mutual statements, using precise backtracking with pruning.

array backtracking bit manipulation enumeration

Problem Statement

You are given a 0-indexed n x n integer array statements where statements[i][j] indicates person i's statement about person j. statements[i][j] can be 0 (person j is bad), 1 (person j is good), or 2 (no statement). Each person is either good or bad, and good people always tell the truth while bad people can lie arbitrarily. You need to determine the maximum number of good people possible consistent with all statements.

No person makes a statement about themselves, meaning statements[i][i] is always 2. The array length n satisfies 2 <= n <= 15, and each statements[i][j] is 0, 1, or 2. You must evaluate all possible assignments of good and bad roles for each person to ensure consistency with the statements.

Examples

Example 1

Input: statements = [[2,1,2],[1,2,2],[2,0,2]]

Output: 2

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

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

Solution Approach

Backtracking with Bitmask Representation

Use a bitmask to represent each assignment of people as good or bad. Iterate through all 2^n possibilities, where each bit indicates if a person is assumed good. For each assignment, validate that all statements by good people are consistent. Track the largest valid assignment to get the maximum number of good people.

Pruning Inconsistent Assignments

While generating assignments, prune any partial configuration as soon as a statement contradiction is detected. If a good person declares another good or bad and it conflicts with the current assignment, backtrack immediately. This reduces the number of total checks and avoids exploring invalid branches, critical for n up to 15.

Maximizing Good People Count

After verifying an assignment is consistent, count the number of good people using bit manipulation or simple summation. Compare with the current maximum and update if higher. Continue until all assignments are checked. Return the maximum count found across all valid configurations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*2^n) because each of the 2^n assignments requires checking up to n statements. Space complexity is O(n) for recursion and temporary assignment storage. Bitmask usage avoids storing all assignments explicitly.

What Interviewers Usually Probe

Do you recognize this as a backtracking problem with bitmask enumeration?
Can you optimize by pruning assignments that violate statements early?
How do you efficiently count good people in each valid assignment?

Common Pitfalls or Variants

Common pitfalls

Failing to validate only statements made by assumed good people.
Not pruning immediately when a contradiction arises, leading to excessive computation.
Confusing the bitmask representation and miscounting good people in final assignments.

Follow-up variants

Allowing statements to include uncertainty beyond 0,1,2, requiring conditional validation.
Maximizing good people under weighted statements where some statements carry more importance.
Finding all valid maximum sets of good people rather than just the count.

FAQ

What is the main strategy for Maximum Good People Based on Statements?

Use backtracking with bitmask enumeration to test all possible good/bad assignments and validate each configuration against the statements.

Why is pruning important in this problem?

Pruning stops exploring assignments as soon as a contradiction is detected, drastically reducing computation for n up to 15.

Can this problem be solved without bit manipulation?

Yes, but using bitmasking simplifies assignment representation and makes counting good people efficient in O(n*2^n) time.

How does GhostInterview assist in checking statements?

It automatically evaluates which people are good or bad in each assignment and flags inconsistencies quickly.

What is the failure mode to watch for?

Assuming bad people always lie can cause incorrect conclusions; only statements by assumed good people must be enforced.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        def check(mask: int) -> int:
            cnt = 0
            for i, row in enumerate(statements):
                if mask >> i & 1:
                    for j, x in enumerate(row):
                        if x < 2 and (mask >> j & 1) != x:
                            return 0
                    cnt += 1
            return cnt

        return max(check(i) for i in range(1, 1 << len(statements)))

Continue Practicing

#2212 maximum points in an archery competition #2044 count number of maximum bitwise or subsets #2397 maximum rows covered by columns