# Maximum Good People Based on Statements
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-good-people-based-on-statements)
Canonical: https://scaleengineer.com/dsa/problems/maximum-good-people-based-on-statements
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [TuSimple](https://scaleengineer.com/companies/tusimple)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-good-people-based-on-statements/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/maximum-good-people-based-on-statements/image1.jpg) 

**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`

# Approaches
## Brute Force with Backtracking
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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a global variable `maxGood = 0`.
- Create a recursive function `solve(index, config)` where `config` is 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 all `n` people.
  - Check if this `config` is logically consistent. To do this, iterate through each person `i` from `0` to `n-1`.
  - If `config[i]` marks person `i` as good:
    - Iterate through all other people `j`.
    - If `statements[i][j]` is not 2 (i.e., a statement exists) and `statements[i][j]` does not match `config[j]`, the configuration is invalid. Return from the validation check.
  - If the configuration is valid after all checks, count the number of good people in `config` and update `maxGood = max(maxGood, count)`.
  - Return from the recursive call.
- **Recursive Step**:
  - First, explore the possibility that person `index` is bad. Set `config[index] = 0` and make a recursive call: `solve(index + 1, config)`.
  - Then, explore the possibility that person `index` is good. Set `config[index] = 1` and make another recursive call: `solve(index + 1, config)`.
- Start the entire process by calling `solve(0, new int[n])`.
- After the initial call returns, `maxGood` will hold the result.

## Brute Force with Iterative Bitmasking
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.
**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`.
**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^n` possibilities, even if the maximum is found early on.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
- Initialize `maxGood = 0`.
- Loop through an integer `mask` from `0` to `(1 << n) - 1`. Each `mask` represents one of the `2^n` possible configurations.
- For each `mask`:
  - Assume this `mask` represents a valid configuration. Set a flag `isCurrentMaskValid = true`.
  - To validate, iterate through each person `i` from `0` to `n-1`.
  - Check if person `i` is assumed to be good in this mask using bitwise AND: `(mask >> i) & 1 == 1`.
  - If person `i` is good, check all their statements. Iterate through each person `j` from `0` to `n-1`.
    - If `statements[i][j]` is not `2` (a statement exists), check for contradiction.
    - A contradiction occurs if `statements[i][j]` does not match the assumed status of person `j` in the mask. The status of `j` is `(mask >> j) & 1`.
    - If a contradiction is found, set `isCurrentMaskValid = false` and break out of the validation loops for this mask.
  - If `isCurrentMaskValid` remains `true` after all checks, the configuration is valid.
    - Count the number of set bits in `mask` using a function like `Integer.bitCount(mask)`.
    - Update `maxGood = max(maxGood, bitCount)`.
- After the loop finishes, return `maxGood`.

## Optimized Bitmasking by Checking from Most to Fewest Good People
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.
**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.
**Pros:** Potentially much faster in practice. If the maximum number of good people is `k`, the algorithm terminates after checking configurations with `n, n-1, ..., k` good people, avoiding checks for `k-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 `k` and then `mask`).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Iterate `k` from `n` down to `0`. Here, `k` represents the target number of good people.
- For each `k`, we need to check all configurations that have exactly `k` good people. A simple way to do this is to iterate through all `mask`s from `0` to `(1 << n) - 1`.
- Inside the mask loop, if `Integer.bitCount(mask)` is not equal to `k`, 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 `i` assumed to be good in the mask, check if their statements about others `j` are consistent with the mask's assumptions.
- If the mask is found to be valid, it means we have found a valid configuration with `k` good people. Since we are iterating `k` downwards, this must be the maximum possible number. We can immediately return `k`.
- 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)))

```