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.
This approach involves using bitmasking to represent all combinations of people being good or bad. Given the constraint that n ≤ 15, there are 2^n possible combinations. For each combination, we verify if it's valid by checking the truth of statements made by good individuals in the combination. The goal is to find the maximum number of good people in any valid configuration.
The code uses bitmasking to generate all possible configurations (2^n) of people being good or bad. A configuration is valid if the truthfulness of statements aligns with the status assigned in that configuration. We iteratively maximize the number of good people found in valid scenarios.
Time Complexity: O(2^n * n^2), as there are 2^n configurations and each takes O(n^2) to validate.
Space Complexity: O(n) for storing status information of people in each iteration.
This approach involves using a backtracking algorithm to explore all possible combinations of good and bad people. With effective pruning, we can reduce the number of unnecessary computations by terminating branches that have already shown contradictions early. This approach makes use of recursion to alternate between possible 'good' or 'bad' states for each person and checks validity accordingly.
This C solution employs a recursive backtracking technique to explore every possible combination of assumptions about people's status being good or bad. The recursive calls alternate status making, checking validity early to prune impossible configurations, maximizing the good count where possible.
Time Complexity: O(2^n * n) since we are attempting each state recursively and checking validity, which costs O(n).
Space Complexity: O(n) due to recursion stack and the status array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Bitmasking to Generate All Combinations | Time Complexity: O(2^n * n^2), as there are 2^n configurations and each takes O(n^2) to validate. |
| Backtracking with Pruning | Time Complexity: O(2^n * n) since we are attempting each state recursively and checking validity, which costs O(n). |
| Default Approach | — |
| 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. |
Maximum Good People Based on Statements| Leeetcode 2151 | Contest 277 | Easy 🔥🔥🔥 | Leetcode Hard • Coding Decoded • 2,165 views views
Watch 9 more video solutions →Practice Maximum Good People Based on Statements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor