Maximum Good People Based on Statements — LeetCode 2151 Python Solution

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.

Example

Input

statements = [[2,1,2],[1,2,2],[2,0,2]]

Output

2

Explanation

Each person makes a single statement.

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

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2151. Maximum Good People Based on Statements is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems