Skip to content

2151. Maximum Good People Based on Statements 👍

Approach 1: DFS

  • Time: $O(n^2 \cdot 2^n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  int maximumGood(vector<vector<int>>& statements) {
    int ans = 0;
    dfs(statements, {}, 0, 0, ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<int>>& statements, vector<int>&& good, int i,
           int count, int& ans) {
    if (i == statements.size()) {
      if (isValid(statements, good))
        ans = max(ans, count);
      return;
    }

    good.push_back(0);  // Assume the i-th person is bad.
    dfs(statements, move(good), i + 1, count, ans);
    good.back() = 1;  // Assume the i-th person is good.
    dfs(statements, move(good), i + 1, count + 1, ans);
    good.pop_back();
  }

  bool isValid(const vector<vector<int>>& statements, const vector<int>& good) {
    for (int i = 0; i < good.size(); ++i) {
      if (!good[i])  // The i-th person is bad, so no need to check.
        continue;
      for (int j = 0; j < statements.size(); ++j) {
        if (statements[i][j] == 2)
          continue;
        if (statements[i][j] != good[j])
          return false;
      }
    }
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int maximumGood(int[][] statements) {
    dfs(statements, new ArrayList<>(), 0, 0);
    return ans;
  }

  private int ans = 0;

  private void dfs(int[][] statements, List<Integer> good, int i, int count) {
    if (i == statements.length) {
      if (isValid(statements, good))
        ans = Math.max(ans, count);
      return;
    }

    good.add(0); // Assume the i-th person is bad.
    dfs(statements, good, i + 1, count);
    good.set(good.size() - 1, 1); // Assume the i-th person is good.
    dfs(statements, good, i + 1, count + 1);
    good.remove(good.size() - 1);
  }

  private boolean isValid(int[][] statements, List<Integer> good) {
    for (int i = 0; i < good.size(); ++i) {
      if (good.get(i) == 0) // The i-th person is bad, so no need to check.
        continue;
      for (int j = 0; j < statements.length; ++j) {
        if (statements[i][j] == 2)
          continue;
        if (statements[i][j] != good.get(j))
          return false;
      }
    }
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
  def maximumGood(self, statements: List[List[int]]) -> int:
    n = len(statements)
    ans = 0

    def isValid(good: List[int]) -> bool:
      for i, g in enumerate(good):
        if not g:  # The i-th person is bad, so no need to check.
          continue
        for j in range(n):
          if statements[i][j] == 2:
            continue
          if statements[i][j] != good[j]:
            return False
      return True

    def dfs(good: List[int], i: int, count: int) -> None:
      nonlocal ans
      if i == n:
        if isValid(good):
          ans = max(ans, count)
        return

      good.append(0)  # Assume the i-th person is bad.
      dfs(good, i + 1, count)
      good[-1] = 1  # Assume the i-th person is good.
      dfs(good, i + 1, count + 1)
      good.pop()

    dfs([], 0, 0)
    return ans

Approach 2: Bitmask

  • Time: $O(n^2 \cdot 2^n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int maximumGood(vector<vector<int>>& statements) {
    const int maxMask = 1 << statements.size();
    int ans = 0;

    for (unsigned mask = 0; mask < maxMask; ++mask)
      if (isValid(statements, mask))
        ans = max(ans, popcount(mask));

    return ans;
  }

 private:
  bool isValid(const vector<vector<int>>& statements, int mask) {
    for (int i = 0; i < statements.size(); ++i) {
      if ((mask >> i & 1) == 0)  // The i-th person is bad, so no need to check.
        continue;
      for (int j = 0; j < statements.size(); ++j) {
        if (statements[i][j] == 2)
          continue;
        if (statements[i][j] != (mask >> j & 1))
          return false;
      }
    }
    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int maximumGood(int[][] statements) {
    final int maxMask = 1 << statements.length;
    int ans = 0;

    for (int mask = 0; mask < maxMask; ++mask)
      if (isValid(statements, mask))
        ans = Math.max(ans, Integer.bitCount(mask));

    return ans;
  }

  private boolean isValid(int[][] statements, int mask) {
    for (int i = 0; i < statements.length; ++i) {
      if ((mask >> i & 1) == 0) // The i-th person is bad, so no need to check.
        continue;
      for (int j = 0; j < statements.length; ++j) {
        if (statements[i][j] == 2)
          continue;
        if (statements[i][j] != (mask >> j & 1))
          return false;
      }
    }
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maximumGood(self, statements: List[List[int]]) -> int:
    n = len(statements)

    def isValid(mask: int) -> bool:
      for i in range(n):
        # The i-th person is bad, so no need to check.
        if (mask >> i & 1) == 0:
          continue
        for j in range(n):
          if statements[i][j] == 2:
            continue
          if statements[i][j] != (mask >> j & 1):
            return False
      return True

    return max(mask.bit_count()
               for mask in range(1 << n)
               if isValid(mask))