2151. Maximum Good People Based on Statements LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2151. Maximum Good People Based on Statements LeetCode Solution with the best time and space complexity. The solution to Maximum Good People Based on Statements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Good People Based on Statements solution in C++
Maximum Good People Based on Statements solution in Java
Maximum Good People Based on Statements solution in Python
Additional Resources

2151. Maximum Good People Based on Statements LeetCode Solution image

Problem Statement of Maximum Good People Based on Statements

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:

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].length
2 <= n <= 15
statements[i][j] is either 0, 1, or 2.
statements[i][i] == 2

Complexity Analysis

Time Complexity: O(n^2 \cdot 2^n)
Space Complexity: O(n)

2151. Maximum Good People Based on Statements LeetCode Solution in C++

class Solution {
 public:
  int maximumGood(vector<vector<int>>& statements) {
    int ans = 0;
    dfs(statements, {}, 0, 0, ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& statements, vector<int>&& good, int i,
           int count, int& ans) {
    if (i == statements.size()) {
      if (isValid(statements, good))
        ans = max(ans, count);
      return;
    }

    good.push_back(0);  // Assume the i-th person is bad.
    dfs(statements, std::move(good), i + 1, count, ans);
    good.back() = 1;  // Assume the i-th person is good.
    dfs(statements, std::move(good), i + 1, count + 1, ans);
    good.pop_back();
  }

  bool isValid(const vector<vector<int>>& statements, const vector<int>& good) {
    for (int i = 0; i < good.size(); ++i) {
      if (!good[i])  // The i-th person is bad, so no need to check.
        continue;
      for (int j = 0; j < statements.size(); ++j) {
        if (statements[i][j] == 2)
          continue;
        if (statements[i][j] != good[j])
          return false;
      }
    }
    return true;
  }
};
/* code provided by PROGIEZ */

2151. Maximum Good People Based on Statements LeetCode Solution in Java

class Solution {
  public int maximumGood(int[][] statements) {
    dfs(statements, new ArrayList<>(), 0, 0);
    return ans;
  }

  private int ans = 0;

  private void dfs(int[][] statements, List<Integer> good, int i, int count) {
    if (i == statements.length) {
      if (isValid(statements, good))
        ans = Math.max(ans, count);
      return;
    }

    good.add(0); // Assume the i-th person is bad.
    dfs(statements, good, i + 1, count);
    good.set(good.size() - 1, 1); // Assume the i-th person is good.
    dfs(statements, good, i + 1, count + 1);
    good.remove(good.size() - 1);
  }

  private boolean isValid(int[][] statements, List<Integer> good) {
    for (int i = 0; i < good.size(); ++i) {
      if (good.get(i) == 0) // The i-th person is bad, so no need to check.
        continue;
      for (int j = 0; j < statements.length; ++j) {
        if (statements[i][j] == 2)
          continue;
        if (statements[i][j] != good.get(j))
          return false;
      }
    }
    return true;
  }
}
// code provided by PROGIEZ

2151. Maximum Good People Based on Statements LeetCode Solution in Python

class Solution:
  def maximumGood(self, statements: list[list[int]]) -> int:
    n = len(statements)
    ans = 0

    def isValid(good: list[int]) -> bool:
      for i, g in enumerate(good):
        if not g:  # The i-th person is bad, so no need to check.
          continue
        for j in range(n):
          if statements[i][j] == 2:
            continue
          if statements[i][j] != good[j]:
            return False
      return True

    def dfs(good: list[int], i: int, count: int) -> None:
      nonlocal ans
      if i == n:
        if isValid(good):
          ans = max(ans, count)
        return

      good.append(0)  # Assume the i-th person is bad.
      dfs(good, i + 1, count)
      good[-1] = 1  # Assume the i-th person is good.
      dfs(good, i + 1, count + 1)
      good.pop()

    dfs([], 0, 0)
    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents