Maximum Good People Based on Statements
HardPrompt
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:
0which represents a statement made by personithat personjis a bad person.1which represents a statement made by personithat personjis a good person.2represents that no statement is made by personiabout personj.
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 either0,1, or2.statements[i][i] == 2
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion to perform a brute-force search over all 2^n possible assignments of 'good' or 'bad' to each person. For each complete assignment (a potential 'world'), it checks for logical consistency. If an assignment is consistent, we count the number of good people and update our maximum count.
Algorithm
- Initialize a global variable
maxGood = 0. - Create a recursive function
solve(index, config)whereconfigis an array representing the good/bad status of each person (e.g., 1 for good, 0 for bad). - Base Case: If
index == n, we have a full configuration for allnpeople.- Check if this
configis logically consistent. To do this, iterate through each personifrom0ton-1. - If
config[i]marks personias good:- Iterate through all other people
j. - If
statements[i][j]is not 2 (i.e., a statement exists) andstatements[i][j]does not matchconfig[j], the configuration is invalid. Return from the validation check.
- Iterate through all other people
- If the configuration is valid after all checks, count the number of good people in
configand updatemaxGood = max(maxGood, count). - Return from the recursive call.
- Check if this
- Recursive Step:
- First, explore the possibility that person
indexis bad. Setconfig[index] = 0and make a recursive call:solve(index + 1, config). - Then, explore the possibility that person
indexis good. Setconfig[index] = 1and make another recursive call:solve(index + 1, config).
- First, explore the possibility that person
- Start the entire process by calling
solve(0, new int[n]). - After the initial call returns,
maxGoodwill hold the result.
Walkthrough
We can model this problem as exploring a decision tree. For each person, we have two choices: they are either 'good' or 'bad'. This creates a binary tree of possibilities. A recursive function can naturally traverse this tree.
The function, let's call it solve, will decide the status of one person at a time. For example, solve(personIndex, currentConfiguration) would try setting personIndex to 'bad' and recursively call solve(personIndex + 1, ...) and then try setting personIndex to 'good' and call solve(personIndex + 1, ...) again.
The base case for the recursion is when we have made a decision for all n people. At this point, we have a complete hypothesis (e.g., {P0: good, P1: bad, P2: good}). We must then validate this hypothesis. The validation rule is: all statements made by people assumed to be 'good' must be true. If a person i is assumed 'good', their statement statements[i][j] must match the assumed status of person j. If we find any contradiction, the hypothesis is invalid. If there are no contradictions, the hypothesis is valid, and we update our answer with the number of good people in this valid scenario.
class Solution { int maxGood = 0; int n; int[][] statements; public int maximumGood(int[][] statements) { this.n = statements.length; this.statements = statements; int[] config = new int[n]; solve(0, config); return maxGood; } private void solve(int person, int[] config) { if (person == n) { if (isValid(config)) { int currentGood = 0; for (int status : config) { if (status == 1) { currentGood++; } } maxGood = Math.max(maxGood, currentGood); } return; } // Case 1: Assume person `person` is bad config[person] = 0; solve(person + 1, config); // Case 2: Assume person `person` is good config[person] = 1; solve(person + 1, config); } private boolean isValid(int[] config) { for (int i = 0; i < n; i++) { // We only care about statements from people assumed to be good if (config[i] == 1) { for (int j = 0; j < n; j++) { if (statements[i][j] != 2 && statements[i][j] != config[j]) { return false; // Contradiction } } } } return true; }}Complexity
Time
O(2^n * n^2) - There are `2^n` possible configurations (leaves in the recursion tree). For each configuration, we perform a validation check which involves iterating through all good people (`i`) and their statements about all other people (`j`), taking O(n^2) time.
Space
O(n) - The space is dominated by the depth of the recursion stack, which goes up to `n`. An auxiliary array of size `n` is also used to store the current configuration.
Trade-offs
Pros
Conceptually straightforward, as it directly models the decision-making process for each person.
Guaranteed to find the correct answer by exhaustively checking all possibilities.
Cons
Typically slower than an equivalent iterative solution due to the overhead of function calls for recursion.
Requires extra space for the recursion call stack, which can be a concern for very deep recursion (though not an issue with n <= 15).
This approach uses bitmasking to represent the 2^n possible assignments of 'good' or 'bad' people. An n-bit integer (a mask) is used, where the i-th bit corresponds to person i. A '1' means good, and a '0' means bad. We iterate through every possible mask, check its validity, and keep track of the maximum number of good people found in a valid configuration.
Algorithm
- Initialize
maxGood = 0. - Loop through an integer
maskfrom0to(1 << n) - 1. Eachmaskrepresents one of the2^npossible configurations. - For each
mask:- Assume this
maskrepresents a valid configuration. Set a flagisCurrentMaskValid = true. - To validate, iterate through each person
ifrom0ton-1. - Check if person
iis assumed to be good in this mask using bitwise AND:(mask >> i) & 1 == 1. - If person
iis good, check all their statements. Iterate through each personjfrom0ton-1.- If
statements[i][j]is not2(a statement exists), check for contradiction. - A contradiction occurs if
statements[i][j]does not match the assumed status of personjin the mask. The status ofjis(mask >> j) & 1. - If a contradiction is found, set
isCurrentMaskValid = falseand break out of the validation loops for this mask.
- If
- If
isCurrentMaskValidremainstrueafter all checks, the configuration is valid.- Count the number of set bits in
maskusing a function likeInteger.bitCount(mask). - Update
maxGood = max(maxGood, bitCount).
- Count the number of set bits in
- Assume this
- After the loop finishes, return
maxGood.
Walkthrough
Instead of recursion, we can implement the exhaustive search iteratively. This is often more efficient in practice by avoiding function call overhead. Each of the 2^n scenarios can be uniquely represented by an n-bit integer, where the i-th bit being 1 means person i is good, and 0 means they are bad.
We can simply loop a variable, say mask, from 0 (binary 00...0, everyone is bad) to 2^n - 1 (binary 11...1, everyone is good). For each mask, we perform the same validation logic as in the backtracking approach. We check if the statements made by the people designated as 'good' by the current mask are consistent with the roles assigned by that same mask. If (mask >> i) & 1 is 1, person i is good, and we must verify their statements. Their statement statements[i][j] must equal (mask >> j) & 1 for all j where a statement is made. If the mask is valid, we count the number of set bits (good people) and update our maximum.
class Solution { public int maximumGood(int[][] statements) { int n = statements.length; int maxGood = 0; // Iterate through all 2^n possible scenarios (masks) for (int mask = 0; mask < (1 << n); mask++) { if (isValid(mask, n, statements)) { // If the scenario is valid, update maxGood with the number of good people maxGood = Math.max(maxGood, Integer.bitCount(mask)); } } return maxGood; } private boolean isValid(int mask, int n, int[][] statements) { for (int i = 0; i < n; i++) { // Check statements of people assumed to be good in this mask if (((mask >> i) & 1) == 1) { for (int j = 0; j < n; j++) { if (statements[i][j] != 2) { // The statement must match the assumed status of person j if (statements[i][j] != ((mask >> j) & 1)) { return false; // Contradiction found } } } } } return true; // No contradictions found }}Complexity
Time
O(2^n * n^2) - We iterate through `2^n` masks. For each mask, the `isValid` function takes O(n^2) time in the worst case, as it may iterate through all `n` people (as speakers) and another `n` people (as subjects).
Space
O(1) - This approach uses only a few variables for loops and the maximum count, requiring constant extra space regardless of the input size `n`.
Trade-offs
Pros
More efficient than the recursive approach due to the elimination of function call overhead.
Bitwise operations are extremely fast, leading to a performant implementation.
Uses constant extra space.
Cons
The worst-case time complexity is still exponential, making it infeasible for larger
n.It always checks all
2^npossibilities, even if the maximum is found early on.
This approach optimizes the iterative bitmasking method. Since we are looking for the maximum number of good people, it's more efficient to start our search by assuming a large number of people are good and working our way down. We iterate from k=n down to 0, and for each k, we check if there exists any valid configuration with exactly k good people. The first k for which we find a valid configuration is guaranteed to be the maximum, so we can return it immediately.
Algorithm
- Iterate
kfromndown to0. Here,krepresents the target number of good people. - For each
k, we need to check all configurations that have exactlykgood people. A simple way to do this is to iterate through allmasks from0to(1 << n) - 1. - Inside the mask loop, if
Integer.bitCount(mask)is not equal tok, we skip this mask and continue to the next one. - If
Integer.bitCount(mask) == k, we proceed to validate this specific mask. - The validation logic is identical to the previous approaches: for every person
iassumed to be good in the mask, check if their statements about othersjare consistent with the mask's assumptions. - If the mask is found to be valid, it means we have found a valid configuration with
kgood people. Since we are iteratingkdownwards, this must be the maximum possible number. We can immediately returnk. - If the outer loop completes, it will at least find a valid configuration for
k=0(everyone is bad, which is always a valid scenario) and return 0.
Walkthrough
The key insight for this optimization is that we don't need to find all valid configurations; we only need the one with the most good people. By searching from the top down, we can stop as soon as we find the first valid scenario.
We loop k from n (everyone is good) down to 0. For each k, we check all bitmasks that have exactly k bits set. A bitmask with k bits set represents a hypothesis where exactly k people are good. We then apply our standard validation function to each of these masks. If any mask with k good people proves to be valid, we have found our answer, and we can immediately return k. This avoids unnecessary checks for configurations with fewer than k good people.
If we check all masks for a given k and none are valid, we decrement k and try again. The process is guaranteed to terminate because the configuration with k=0 (everyone is bad) has no 'good' people making statements, so it is always valid by definition.
class Solution { public int maximumGood(int[][] statements) { int n = statements.length; // Iterate downwards from n (max possible good people) to 0 for (int k = n; k >= 0; k--) { // Check all masks with k bits set // A simpler implementation is to iterate all masks and filter by bit count for (int mask = 0; mask < (1 << n); mask++) { if (Integer.bitCount(mask) != k) { continue; } if (isValid(mask, n, statements)) { // First valid configuration found must be the max return k; } } } return 0; // Should be unreachable for n > 0, as k=0 is always valid } private boolean isValid(int mask, int n, int[][] statements) { for (int i = 0; i < n; i++) { if (((mask >> i) & 1) == 1) { // If person i is good for (int j = 0; j < n; j++) { if (statements[i][j] != 2 && statements[i][j] != ((mask >> j) & 1)) { return false; // Contradiction } } } } return true; }}Complexity
Time
O(2^n * n^2) - The worst-case complexity is the same as the other brute-force methods. However, the average-case performance is significantly better if the answer is a large number, due to the early exit.
Space
O(1) - No extra space proportional to the input size is needed.
Trade-offs
Pros
Potentially much faster in practice. If the maximum number of good people is
k, the algorithm terminates after checking configurations withn, n-1, ..., kgood people, avoiding checks fork-1, ..., 0.Maintains the same low O(1) space complexity as the standard iterative approach.
Guaranteed to be correct and is the most efficient approach for this problem's constraints.
Cons
The worst-case time complexity remains
O(2^n * n^2), which occurs if the only valid configuration is with 0 good people.The code can look slightly more complex with the nested loop structure (iterating
kand thenmask).
Solutions
Solution
class Solution {public int maximumGood(int[][] statements) { int ans = 0; for (int mask = 1; mask < 1 << statements.length; ++mask) { ans = Math.max(ans, check(mask, statements)); } return ans; }private int check(int mask, int[][] statements) { int cnt = 0; int n = statements.length; for (int i = 0; i < n; ++i) { if (((mask >> i) & 1) == 1) { for (int j = 0; j < n; ++j) { int v = statements[i][j]; if (v < 2 && ((mask >> j) & 1) != v) { return 0; } } ++cnt; } } return cnt; }}class Solution {public: int maximumGood(vector<vector<int>> &statements) { int ans = 0; for (int mask = 1; mask < 1 << statements.size(); ++mask) ans = max(ans, check(mask, statements)); return ans; } int check(int mask, vector<vector<int>> &statements) { int cnt = 0; int n = statements.size(); for (int i = 0; i < n; ++i) { if ((mask >> i) & 1) { for (int j = 0; j < n; ++j) { int v = statements[i][j]; if (v < 2 && ((mask >> j) & 1) != v) return 0; } ++cnt; } } return cnt; }};class Solution: def maximumGood(self, statements: List[List[int]]) -> int: def check(mask): cnt = 0 for i, s in enumerate(statements): if (mask >> i) & 1: for j, v in enumerate(s): if v < 2 and ((mask >> j) & 1) != v: return 0 cnt += 1 return cnt return max(check(mask) for mask in range(1, 1 << len(statements)))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.