LeetCode 2151 - Maximum Good People Based on Statements

The problem asks us to determine the maximum number of good people in a group given a set of statements about each other. Each person can either be good (always tells the truth) or bad (may lie or tell the truth).

leetcodehardarraybacktrackingbit-manipulationenumeration

LeetCode Problem 2151

Difficulty: 🔴 Hard
Topics: Array, Backtracking, Bit Manipulation, Enumeration

Solution

Problem Understanding

The problem asks us to determine the maximum number of good people in a group given a set of statements about each other. Each person can either be good (always tells the truth) or bad (may lie or tell the truth). The input is a square 2D array statements of size n x n, where statements[i][j] represents person i's statement about person j. The values have the following meanings: 0 means "bad," 1 means "good," and 2 means "no statement." Additionally, each person never makes a statement about themselves, i.e., statements[i][i] = 2.

The goal is to find an assignment of good and bad people that maximizes the number of good people while remaining consistent with the statements made by the good people. A good person's statements must be entirely truthful, whereas a bad person's statements can be inconsistent.

The constraints tell us that n is at most 15. This is small enough to allow enumeration of all possible combinations of good and bad people using bit manipulation, since 2^15 = 32,768, which is computationally feasible. Important edge cases include scenarios where everyone is bad, everyone is good, or where statements are contradictory and cannot all be satisfied.

Approaches

Brute Force

A naive brute-force approach would be to try every possible combination of people being good or bad and check if it is valid. We generate all 2^n combinations of good/bad assignments and, for each assignment, verify that all statements made by good people are consistent. If they are, we count the number of good people and track the maximum. This approach is correct but can be slow for n=15 if not implemented efficiently.

Optimal Approach

The key insight is that we can encode each assignment as a bitmask of length n, where a 1 represents a good person and a 0 represents a bad person. Using this encoding, we can efficiently iterate over all combinations and validate each assignment using simple bitwise operations or loops. This reduces overhead compared to generating sets or arrays of people. The validation checks only the statements of those marked as good, ignoring statements from bad people, which simplifies consistency checking.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n^2) O(n) Check all combinations explicitly
Bitmask Enumeration O(2^n * n^2) O(1) Efficient bitmasking for assignment representation

Algorithm Walkthrough

  1. Represent each possible assignment of good and bad people as an n-bit integer, where the ith bit is 1 if person i is good, otherwise 0.
  2. Initialize a variable max_good to track the maximum number of good people found across valid assignments.
  3. Iterate through all possible bitmasks from 0 to 2^n - 1.
  4. For each bitmask, assume it represents the current assignment of good/bad people.
  5. Check the validity of this assignment by iterating over each person. If the person is marked as good, their statements must be consistent with the assignment. For each statement, if it contradicts the assumed role of another person, mark the assignment as invalid.
  6. If the assignment is valid, count the number of good people in the bitmask and update max_good if this number is higher.
  7. After checking all assignments, return max_good.

Why it works: By enumerating all possible good/bad assignments and checking consistency only against statements from good people, we ensure that any valid configuration is considered. Since we explicitly count good people and maximize, the result is guaranteed to be the largest possible number.

Python Solution

from typing import List

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        n = len(statements)
        max_good = 0
        
        # Iterate over all possible assignments of good/bad people
        for mask in range(1 << n):
            valid = True
            for i in range(n):
                if (mask >> i) & 1:  # person i is good
                    for j in range(n):
                        if statements[i][j] == 2:
                            continue
                        if statements[i][j] != ((mask >> j) & 1):
                            valid = False
                            break
                    if not valid:
                        break
            if valid:
                max_good = max(max_good, bin(mask).count('1'))
        
        return max_good

In this implementation, we use a bitmask to represent the current assignment of good and bad people. We only check the statements of people marked as good, ensuring that their claims match the assignment. If consistent, we count the good people and update the maximum.

Go Solution

func maximumGood(statements [][]int) int {
    n := len(statements)
    maxGood := 0
    
    for mask := 0; mask < (1 << n); mask++ {
        valid := true
        for i := 0; i < n; i++ {
            if (mask>>i)&1 == 1 { // person i is good
                for j := 0; j < n; j++ {
                    if statements[i][j] == 2 {
                        continue
                    }
                    if statements[i][j] != ((mask>>j)&1) {
                        valid = false
                        break
                    }
                }
                if !valid {
                    break
                }
            }
        }
        if valid {
            count := 0
            for i := 0; i < n; i++ {
                if (mask>>i)&1 == 1 {
                    count++
                }
            }
            if count > maxGood {
                maxGood = count
            }
        }
    }
    
    return maxGood
}

Go-specific considerations include explicit integer operations for bitmasking and manual counting of set bits instead of using bin(mask).count('1') as in Python.

Worked Examples

Example 1: [[2,1,2],[1,2,2],[2,0,2]]

mask interpretation valid? good count
011 0 bad, 1 good, 2 good false -
101 0 good, 1 bad, 2 good false -
110 0 bad, 1 good, 2 good false -
010 0 bad, 1 good, 2 bad true 1
011 0 bad, 1 good, 2 good false -
101 0 good, 1 bad, 2 good false -
100 0 good, 1 bad, 2 bad true 1
010 0 bad, 1 good, 2 bad true 1
110 0 good, 1 good, 2 bad true 2

Maximum good people is 2.

Example 2: [[2,0],[0,2]]

mask interpretation valid? good count
00 0 bad, 1 bad true 0
01 0 bad, 1 good true 1
10 0 good, 1 bad true 1
11 0 good, 1 good false -

Maximum good people is 1.

Complexity Analysis

Measure Complexity Explanation
Time O(2^n * n^2) We enumerate all 2^n assignments, checking each of n people against n statements
Space O(1) Bitmasking uses constant extra space aside from input

The time complexity is feasible since n <= 15, giving a maximum of 32,768 masks to check, each requiring at most 225 comparisons for n=15.

Test Cases

# Provided examples
assert Solution().maximumGood([[2,1,2],[1,2,2],[2,0,2]]) == 2  # maximum 2 good people
assert Solution().maximumGood([[2,0],[0,2]]) == 1  # maximum 1 good person

# Edge cases
assert Solution().maximumGood([[2,2],[2,2]]) == 2  # everyone is good, no statements
assert Solution().maximumGood([[2,0,0],[0,2,0],[0,0,2]]) == 1  # only one person can be good
assert Solution().maximumGood([[2,1,1],[1,2,1],[1,1,2]]) == 3  # all statements consistent, everyone good
Test Why
[[2,1,2],[1,2,2],[2,0,2]] Provided example with mixed statements
[[2,0],[0,2]] Minimal case with two people
[[2,2],[2,2]] No statements, everyone can be good
`[[2,0