Leetcode #2151: Maximum Good People Based on Statements
In this guide, we solve Leetcode #2151 Maximum Good People Based on Statements in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Bit Manipulation, Array, Backtracking, Enumeration
Intuition
We must explore combinations of choices, but many branches can be pruned early.
Backtracking enumerates valid candidates while keeping the search space under control.
Approach
Use DFS to build candidates step by step, and backtrack when constraints are violated.
Pruning keeps the exploration practical for typical constraints.
Steps:
- Define the decision tree.
- DFS through choices and backtrack.
- Prune invalid paths early.
Example
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.
Python Solution
class Solution:
def maximumGood(self, statements: List[List[int]]) -> int:
def check(mask: int) -> int:
cnt = 0
for i, row in enumerate(statements):
if mask >> i & 1:
for j, x in enumerate(row):
if x < 2 and (mask >> j & 1) != x:
return 0
cnt += 1
return cnt
return max(check(i) for i in range(1, 1 << len(statements)))
Complexity
The time complexity is Exponential (worst case). The space complexity is O(depth).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.