Maximum Good People Based on Statements

Ah, the classic dilemma of determining who among us is “good” and who is “bad.” If only life were as simple as a game of “Guess Who?” But alas, here we are, trying to figure out the maximum number of good people based on their statements. Spoiler alert: it’s not as straightforward as it seems!

Imagine you’re at a party, and everyone is making claims about each other. “I swear, Bob is a saint!” says Alice, while Bob is busy saying, “Alice? Oh, she’s definitely up to no good!” Now, how do we figure out who’s telling the truth? Welcome to the world of logic puzzles, where everyone is a suspect, and the truth is as elusive as the last slice of pizza at a gathering.

Links to Other Solutions

Java Solution
Python Solution

Problem Description

The problem at hand is to determine the maximum number of “good” people based on their statements about each other. Each person can either be “good,” “bad,” or neutral (indicated by a 2). A good person tells the truth about others, while a bad person can say anything. Your task is to find the maximum number of good people that can exist without contradicting their statements.

Code Solution


class Solution {
 public:
  int maximumGood(vector>& statements) {
    int ans = 0;
    dfs(statements, {}, 0, 0, ans);
    return ans;
  }

 private:
  void dfs(const vector>& statements, vector&& 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, std::move(good), i + 1, count, ans);
    good.back() = 1;  // Assume the i-th person is good.
    dfs(statements, std::move(good), i + 1, count + 1, ans);
    good.pop_back();
  }

  bool isValid(const vector>& statements, const vector& 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;
  }
};

Approach Explanation

The approach used in this solution is a depth-first search (DFS) to explore all possible combinations of good and bad people. The function dfs recursively checks each person, assuming they are either good or bad, and counts the maximum number of good people that can exist without contradicting the statements made. The isValid function checks if the current configuration of good and bad people is consistent with the statements.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(2^N), where N is the number of people.
Space Complexity	O(N) for the recursion stack and the storage of the good vector.

Real-World Example

Imagine a workplace where employees are making statements about each other’s performance. If Alice claims Bob is a top performer, but Bob says Alice is slacking off, you have a classic case of conflicting statements. By applying the logic from our problem, you can determine the maximum number of employees who can be considered top performers without contradicting each other’s claims.