Watch 10 video solutions for Maximum Good People Based on Statements, a hard level problem involving Array, Backtracking, Bit Manipulation. This walkthrough by Coding Decoded has 2,165 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are two types of persons:
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].length2 <= n <= 15statements[i][j] is either 0, 1, or 2.statements[i][i] == 2Problem Overview: You are given a matrix where statements[i][j] represents what person i says about person j. A good person always tells the truth, while a bad person may lie or tell the truth. The task is to determine the maximum number of people that can be labeled good without creating contradictions.
Approach 1: Bitmasking to Generate All Combinations (Time: O(2^n * n^2), Space: O(1))
The key observation: each person can either be good or bad, which forms 2^n possible assignments. Use a bitmask from 0 to (1<<n)-1 where each bit indicates whether a person is considered good. For each mask, iterate over all people marked good and validate their statements against the assumed assignments. If a good person claims someone is good but the mask marks them bad (or vice versa), the configuration is invalid. Count the number of set bits in valid masks and keep the maximum. This brute-force enumeration works because n ≤ 15, making 2^n manageable. Bit operations make the implementation compact and fast. This approach heavily uses bit manipulation and enumeration techniques.
Approach 2: Backtracking with Pruning (Time: O(2^n * n), Space: O(n))
Instead of generating every configuration blindly, you can build assignments incrementally using backtracking. At each index, decide whether the current person is good or bad and maintain a running assignment array. When you mark someone as good, immediately verify that all their statements remain consistent with previously assigned people. If a contradiction appears, stop exploring that branch early (pruning). This significantly reduces the search space compared to checking every full mask. The recursion explores valid states only, updating the maximum number of good people whenever a full assignment is reached. This method naturally models the constraint-checking process and is a common pattern in backtracking problems.
Recommended for interviews: Bitmask enumeration is the most common interview solution because it is simple and deterministic. You iterate through all possible assignments and validate them directly. Backtracking with pruning demonstrates stronger problem-solving skills since it avoids unnecessary checks and reduces the search space, but the bitmask approach is usually faster to implement under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmasking to Generate All Combinations | O(2^n * n^2) | O(1) | Best when n ≤ 15 and you want a straightforward brute-force validation of all assignments. |
| Backtracking with Pruning | O(2^n * n) worst case | O(n) | Useful when early contradictions allow pruning large parts of the search tree. |