Maximum good people based on statements

Array Backtracking Bit Manipulation Enumeration

52.3% acceptance

Feb 25, 2026

533

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. statements[i][j]: 0 = i says j is bad, 1 = i says j is good, 2 = no statement. Return the maximum number of people who can be good based on the statements.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_good(statements: Vec<Vec<i32>>) -> i32 {
    let n = statements.len();
    let mut best = 0;
    // Try each subset as the "good" people
    for mask in 0u32..(1 << n) {
      let mut valid = true;
      'outer: for i in 0..n {
        if mask & (1 << i) == 0 {
          continue; // i is bad, no constraints from bad people
        }
        // i is good: all their statements must be consistent
        for j in 0..n {
          let stmt = statements[i][j];
          if stmt == 1 && (mask & (1 << j) == 0) {
            // i says j is good but j is bad
            valid = false;
            break 'outer;
          }
          if stmt == 0 && (mask & (1 << j) != 0) {
            // i says j is bad but j is good
            valid = false;
            break 'outer;
          }
        }
      }
      if valid {
        best = best.max(mask.count_ones() as i32);
      }
    }
    best
  }
}