Skip to main content
Talentd

Maximum Good People Based on Statements - Solution & Explanation

HardArrayBacktrackingBit ManipulationEnumeration21 min readAsked at: Microsoft, Oracle, TuSimple
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for storing status information of people in each iteration.

Backtracking with Pruning

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bitmasking to Generate All CombinationsO(2^n * n^2)O(1)Best when n ≤ 15 and you want a straightforward brute-force validation of all assignments.
Backtracking with PruningO(2^n * n) worst caseO(n)Useful when early contradictions allow pruning large parts of the search tree.

Video Solution

Maximum Good People Based on Statements| Leeetcode 2151 | Contest 277 | Easy 🔥🔥🔥 | Leetcode Hard • Coding Decoded • 2,188 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Good People Based on Statements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Score Words Formed by Letters