Maximum Good People Based on Statements solution and explanation
9 more videos on this problem
Maximum Good People Based on Statements| Leeetcode 2151 | Contest 277 | Easy 🔥🔥🔥 | Leetcode HardCoding Decoded · 12:42 · 2K views
Maximum Good People Based on Statements | Leetcode 2151 | Weekly Contest 277 Solution | JavaPepcoding · 40:40 · 1K views
2151 Maximum Good People Based on Statements || Weekly Contest 277 || LeetCode 2151 || Hard || BestBro Coders · 28:15 · 1K views
2151. Maximum Good People Based on Statements (Leetcode Hard)Programming Live with Larry · 14:39 · 969 views
(Hard)Maximum Good People Based on Statements | Weekly Contest 277Hitesh Tripathi · 15:57 · 604 views
【每日一题】LeetCode 2151. Maximum Good People Based on StatementsHuifeng Guan · 15:04 · 456 views
BitMasking Tutorial - Maximum Good People Based on Statements - PythonCheatCode Ninja · 16:57 · 411 views
2151. Maximum Good People Based on Statements: Weekly Contest 277viralSongs · 11:35 · 329 views
Maximum Good People Based on Statements | Leetcode Weekly Contest 277 | Recursion | Backtrack | DSATejpratap Pandey · 21:41 · 198 views
LeetCode 2151 Maximum Good People Based on Statements - PythonLight Of Truth · 20:15 · 97 views
The 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:
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
Approach overview
Problem 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 1: Bitmasking to Generate All Combinations
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.
def check_valid(status, statements):
n = len(status)
for i in range(n):
if status[i]: # Only validate the statements for 'good' people
for j in range(n):
if statements[i][j] != 2:
should_be_good = statements[i][j] == 1
if status[j] != should_be_good:
return False
return True
def maxGoodPeople(statements):
n = len(statements)
max_good = 0
total_combinations = 1 << n # 2^n
for mask in range(total_combinations):
status = [False] * n
count_good = 0
for i in range(n):
if (mask & (1 << i)) != 0:
status[i] = True
count_good += 1
if check_valid(status, statements):
max_good = max(max_good, count_good)
return max_good
statements = [[2, 1, 2], [1, 2, 2], [2, 0, 2]]
print(maxGoodPeople(statements)) # Output: 2public class Main {
public static boolean checkValid(boolean[] status, int[][] statements, int n) {
for (int i = 0; i < n; i++) {
if (status[i]) {
for (int j = 0; j < n; j++) {
if (statements[i][j] != 2) {
boolean shouldBeGood = statements[i][j] == 1;
if (status[j] != shouldBeGood) {
return false;
}
}
}
}
}
return true;
}
public static int maxGoodPeople(int[][] statements) {
int n = statements.length;
int maxGood = 0;
int totalCombinations = 1 << n;
for (int mask = 0; mask < totalCombinations; mask++) {
boolean[] status = new boolean[n];
int countGood = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
status[i] = true;
countGood++;
}
}
if (checkValid(status, statements, n)) {
maxGood = Math.max(maxGood, countGood);
}
}
return maxGood;
}
public static void main(String[] args) {
int[][] statements = {{2, 1, 2}, {1, 2, 2}, {2, 0, 2}};
System.out.println(maxGoodPeople(statements)); // Output: 2
}
}#include <vector>
#include <iostream>
using namespace std;
bool check_valid(const vector<bool>& status, const vector<vector<int>>& statements) {
int n = status.size();
for (int i = 0; i < n; ++i) {
if (status[i]) {
for (int j = 0; j < n; ++j) {
if (statements[i][j] != 2) {
bool should_be_good = statements[i][j] == 1;
if (status[j] != should_be_good) {
return false;
}
}
}
}
}
return true;
}
int maxGoodPeople(vector<vector<int>>& statements) {
int n = statements.size();
int max_good = 0;
int total_combinations = 1 << n;
for (int mask = 0; mask < total_combinations; ++mask) {
vector<bool> status(n);
int count_good = 0;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
status[i] = true;
count_good++;
}
else {
status[i] = false;
}
}
if (check_valid(status, statements)) {
max_good = max(max_good, count_good);
}
}
return max_good;
}
int main() {
vector<vector<int>> statements = {{2, 1, 2}, {1, 2, 2}, {2, 0, 2}};
cout << maxGoodPeople(statements) << endl; // Output: 2
return 0;
}function checkValid(status, statements) {
const n = status.length;
for (let i = 0; i < n; i++) {
if (status[i]) {
for (let j = 0; j < n; j++) {
if (statements[i][j] !== 2) {
const shouldBeGood = statements[i][j] === 1;
if (status[j] !== shouldBeGood) {
return false;
}
}
}
}
}
return true;
}
function maxGoodPeople(statements) {
const n = statements.length;
let maxGood = 0;
const totalCombinations = 1 << n;
for (let mask = 0; mask < totalCombinations; mask++) {
const status = Array(n).fill(false);
let countGood = 0;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) !== 0) {
status[i] = true;
countGood++;
}
}
if (checkValid(status, statements)) {
maxGood = Math.max(maxGood, countGood);
}
}
return maxGood;
}
const statements = [[2, 1, 2], [1, 2, 2], [2, 0, 2]];
console.log(maxGoodPeople(statements)); // Output: 2#include <stdio.h>
#include <stdbool.h>
int check_valid(bool* status, int** statements, int n) {
for (int i = 0; i < n; i++) {
if (status[i]) { // Only consider statements of 'good' people
for (int j = 0; j < n; j++) {
if (statements[i][j] != 2) {
bool should_be_good = statements[i][j] == 1;
if (status[j] != should_be_good) {
return 0;
}
}
}
}
}
return 1;
}
int maxGoodPeople(int** statements, int n) {
int max_good = 0;
int total_combinations = 1 << n; // 2^n
for (int mask = 0; mask < total_combinations; mask++) {
bool status[15];
int count_good = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
status[i] = true;
count_good++;
} else {
status[i] = false;
}
}
if (check_valid(status, statements, n)) {
if (count_good > max_good) {
max_good = count_good;
}
}
}
return max_good;
}
int main() {
int n = 3;
int statements[3][3] = {{2, 1, 2}, {1, 2, 2}, {2, 0, 2}};
int* ptr_statements[3] = {statements[0], statements[1], statements[2]};
printf("%d\n", maxGoodPeople(ptr_statements, n)); // Output: 2
return 0;
}using System;
public class Solution {
public static bool CheckValid(bool[] status, int[][] statements, int n) {
for (int i = 0; i < n; i++) {
if (status[i]) {
for (int j = 0; j < n; j++) {
if (statements[i][j] != 2) {
bool shouldBeGood = statements[i][j] == 1;
if (status[j] != shouldBeGood) {
return false;
}
}
}
}
}
return true;
}
public static int MaxGoodPeople(int[][] statements) {
int n = statements.Length;
int maxGood = 0;
int totalCombinations = 1 << n;
for (int mask = 0; mask < totalCombinations; mask++) {
bool[] status = new bool[n];
int countGood = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
status[i] = true;
countGood++;
}
}
if (CheckValid(status, statements, n)) {
maxGood = Math.Max(maxGood, countGood);
}
}
return maxGood;
}
public static void Main(string[] args) {
int[][] statements = new int[][] { new int[] { 2, 1, 2 }, new int[] { 1, 2, 2 }, new int[] { 2, 0, 2 } };
Console.WriteLine(MaxGoodPeople(statements)); // Output: 2
}
}The Python implementation leverages bitmasking to iterate over all possible configurations of good/bad statuses for each person. By validating these configurations using the statements matrix, the solution seeks to maximize the number of good individuals.
Time Complexity: O(2^n * n^2) as each configuration is generated and validated.
Space Complexity: O(n) for tracking the status of each person.
Approach 2: Backtracking with Pruning
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.
max_good = 0
def backtrack(status, statements, index, good_count):
global max_good
n = len(status)
if index == n:
valid = True
for i in range(n):
if status[i] == 1: # 'Good' person
for j in range(n):
if statements[i][j] != 2 and statements[i][j] != status[j]:
valid = False
break
if not valid:
break
if valid:
max_good = max(max_good, good_count)
return
# Assume current index is a good person
status[index] = 1
backtrack(status, statements, index + 1, good_count + 1)
# Assume current index is a bad person
status[index] = 0
backtrack(status, statements, index + 1, good_count)
def max_good_people(statements):
global max_good
max_good = 0
n = len(statements)
status = [0] * n
backtrack(status, statements, 0, 0)
return max_good
statements = [[2, 1, 2], [1, 2, 2], [2, 0, 2]]
print(max_good_people(statements)) # Output: 2public class Main {
static int maxGood = 0;
public static void backtrack(int[] status, int[][] statements, int index, int goodCount) {
int n = status.length;
if (index == n) {
boolean valid = true;
for (int i = 0; i < n && valid; i++) {
if (status[i] == 1) {
for (int j = 0; j < n; j++) {
if (statements[i][j] != 2 && statements[i][j] != status[j]) {
valid = false;
break;
}
}
}
}
if (valid) {
maxGood = Math.max(maxGood, goodCount);
}
return;
}
status[index] = 1;
backtrack(status, statements, index + 1, goodCount + 1);
status[index] = 0;
backtrack(status, statements, index + 1, goodCount);
}
public static int maxGoodPeople(int[][] statements) {
int n = statements.length;
maxGood = 0;
int[] status = new int[n];
backtrack(status, statements, 0, 0);
return maxGood;
}
public static void main(String[] args) {
int[][] statements = {{2, 1, 2}, {1, 2, 2}, {2, 0, 2}};
System.out.println(maxGoodPeople(statements)); // Output: 2
}
}#include <vector>
#include <iostream>
using namespace std;
int maxGood = 0;
void backtrack(vector<int>& status, vector<vector<int>>& statements, int index, int goodCount) {
int n = status.size();
if (index == n) {
bool valid = true;
for (int i = 0; i < n && valid; ++i) {
if (status[i] == 1) {
for (int j = 0; j < n; ++j) {
if (statements[i][j] != 2 && statements[i][j] != status[j]) {
valid = false;
break;
}
}
}
}
if (valid) {
maxGood = max(maxGood, goodCount);
}
return;
}
status[index] = 1;
backtrack(status, statements, index + 1, goodCount + 1);
status[index] = 0;
backtrack(status, statements, index + 1, goodCount);
}
int maxGoodPeople(vector<vector<int>>& statements) {
int n = statements.size();
vector<int> status(n, 0);
backtrack(status, statements, 0, 0);
return maxGood;
}
int main() {
vector<vector<int>> statements = {{2, 1, 2}, {1, 2, 2}, {2, 0, 2}};
cout << maxGoodPeople(statements) << endl; // Output: 2
return 0;
}let maxGood = 0;
function backtrack(status, statements, index, goodCount) {
const n = status.length;
if (index === n) {
let valid = true;
for (let i = 0; i < n && valid; i++) {
if (status[i] === 1) {
for (let j = 0; j < n; j++) {
if (statements[i][j] !== 2 && statements[i][j] !== status[j]) {
valid = false;
break;
}
}
}
}
if (valid) {
maxGood = Math.max(maxGood, goodCount);
}
return;
}
status[index] = 1;
backtrack(status, statements, index + 1, goodCount + 1);
status[index] = 0;
backtrack(status, statements, index + 1, goodCount);
}
function maxGoodPeople(statements) {
maxGood = 0;
const n = statements.length;
const status = Array(n).fill(0);
backtrack(status, statements, 0, 0);
return maxGood;
}
const statements = [[2, 1, 2], [1, 2, 2], [2, 0, 2]];
console.log(maxGoodPeople(statements)); // Output: 2#include <stdio.h>
int maxGood = 0;
void backtrack(int* status, int** statements, int n, int index, int goodCount) {
if (index == n) {
int valid = 1;
for (int i = 0; i < n && valid; i++) {
if (status[i] == 1) { // Only validate the statements of 'good' people
for (int j = 0; j < n; j++) {
if (statements[i][j] != 2) {
if (statements[i][j] != status[j]) {
valid = 0;
break;
}
}
}
}
}
if (valid) {
if (goodCount > maxGood) {
maxGood = goodCount;
}
}
return;
}
// Try assuming the current person is good
status[index] = 1;
backtrack(status, statements, n, index + 1, goodCount + 1);
// Try assuming the current person is bad
status[index] = 0;
backtrack(status, statements, n, index + 1, goodCount);
}
int maxGoodPeople(int** statements, int n) {
int status[15] = {0}; // Initialize all to 'bad'
backtrack(status, statements, n, 0, 0);
return maxGood;
}
int main() {
int n = 3;
int statements[3][3] = {{2, 1, 2}, {1, 2, 2}, {2, 0, 2}};
int* ptr_statements[3] = {statements[0], statements[1], statements[2]};
printf("%d\n", maxGoodPeople(ptr_statements, n)); // Output: 2
return 0;
}using System;
public class MainClass {
static int maxGood = 0;
public static void Backtrack(int[] status, int[][] statements, int index, int goodCount) {
int n = status.Length;
if (index == n) {
bool valid = true;
for (int i = 0; i < n && valid; i++) {
if (status[i] == 1) {
for (int j = 0; j < n; j++) {
if (statements[i][j] != 2 && statements[i][j] != status[j]) {
valid = false;
break;
}
}
}
}
if (valid) {
maxGood = Math.Max(maxGood, goodCount);
}
return;
}
status[index] = 1;
Backtrack(status, statements, index + 1, goodCount + 1);
status[index] = 0;
Backtrack(status, statements, index + 1, goodCount);
}
public static int MaxGoodPeople(int[][] statements) {
int n = statements.Length;
maxGood = 0;
int[] status = new int[n];
Backtrack(status, statements, 0, 0);
return maxGood;
}
public static void Main(string[] args) {
int[][] statements = new int[][] { new int[] { 2, 1, 2 }, new int[] { 1, 2, 2 }, new int[] { 2, 0, 2 } };
Console.WriteLine(MaxGoodPeople(statements)); // Output: 2
}
}The Python solution employs backtracking, recursively assuming possible good/bad statuses for each person, terminating branches early that have contradictions following the given statements. It attempts to find the configuration with the most number of good people.
Time Complexity: O(2^n * n) since for each recursive call, linear checks validate the configuration.
Space Complexity: O(n) because it keeps a recursive call stack and an array state.
Approach 3: Default Approach
function maximumGood(statements: number[][]): number {
const n = statements.length;
function check(mask) {
let cnt = 0;
for (let i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
for (let j = 0; j < n; ++j) {
const v = statements[i][j];
if (v < 2 && ((mask >> j) & 1) != v) {
return 0;
}
}
++cnt;
}
}
return cnt;
}
let ans = 0;
for (let mask = 1; mask < 1 << n; ++mask) {
ans = Math.max(ans, check(mask));
}
return ans;
}func maximumGood(statements [][]int) int {
n := len(statements)
check := func(mask int) int {
cnt := 0
for i, s := range statements {
if ((mask >> i) & 1) == 1 {
for j, v := range s {
if v < 2 && ((mask>>j)&1) != v {
return 0
}
}
cnt++
}
}
return cnt
}
ans := 0
for mask := 1; mask < 1<<n; mask++ {
ans = max(ans, check(mask))
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bitmasking to Generate All Combinations | Time Complexity: O(2^n * n^2) as each configuration is generated and validated. |
| Backtracking with Pruning | Time Complexity: O(2^n * n) since for each recursive call, linear checks validate the configuration. |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximum Good People Based on Statements easy or hard?
The problem is classified as Hard because it combines logical reasoning with exponential state exploration. Recognizing that n ≤ 15 allows a bitmask or backtracking solution is the key insight.
Maximum Good People Based on Statements Python/Java solution
In Python or Java, the common implementation iterates through all bitmasks from 0 to (1<<n)-1. For each mask, count the number of good people and verify whether every statement from a good person matches the assumed assignments. If valid, update the maximum count.
How to solve Maximum Good People Based on Statements in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of people being good or bad. The optimal practical solutions rely on enumeration or backtracking, which take O(2^n) time in the worst case due to the exponential number of assignments.
What is the best approach for Maximum Good People Based on Statements?
Bitmask enumeration is the most common approach. Each bitmask represents an assignment of people as good or bad, and you verify whether all statements made by good people are consistent. The algorithm checks up to 2^n configurations and validates each in O(n^2) time.
Is Maximum Good People Based on Statements asked at Google/Amazon/Meta?
Problems involving logical consistency, constraint checking, and bitmask enumeration are common in interviews at companies like Google, Amazon, and Meta. Variants of this problem test reasoning about truth constraints and efficient state exploration.
What data structure is used in Maximum Good People Based on Statements?
The main structure is a 2D array (matrix) storing statements between people. Solutions often use bitmasks to represent subsets of good people, along with loops or recursion to validate constraints between individuals.
What is the time complexity of Maximum Good People Based on Statements?
The typical bitmask solution runs in O(2^n * n^2) time, where n is the number of people. For each of the 2^n assignments, the algorithm verifies statements between pairs of people. Space complexity is O(1) aside from the input.