Maximum Good People Based on Statements LeetCode solution in Java

1
class Solution {
2
  public int maximumGood(int[][] statements) {
3
    int[] result = {0};
4
    maximumGood(statements, new boolean[statements.length], 0, 0, result);
5
    return result[0];
6
  }
7

8
  /*
9
      This function uses backtracking to do the DFS. We are basically constructing all possible scenarios and verifying them.
10

11
      statements (int[][]): This is the input statements.
12
      goodPeople (boolean[]): This array tells who are good and bad in the group.
13
      currentPerson (int): This is the current person that we are verifying.
14
      currentGoodPeople (int): This is the number of the good people identified so far.
15
      result (int[]): This array holds the result, the total number of good people.
16
  */
17
  private void maximumGood(
18
      int[][] statements,
19
      boolean[] goodPeople,
20
      int currentPerson,
21
      int currentGoodPeople,
22
      int[] result) {
23
    if (currentPerson == goodPeople.length) {
24
      result[0] = Math.max(result[0], currentGoodPeople);
25
      return;
26
    }
27

28
    // Now we are going to use backtracking to do DFS.
29

30
    // Scenario 1: Assume the current person is good and verify it.
31
    goodPeople[currentPerson] = true;
32
    // Prune the tree if the sum of unverified people (goodPeople.length - currentPerson) and
33
    // verifyied good people (currentGoodPeople) is less than the result.
34
    if (goodPeople.length - currentPerson + currentGoodPeople < result[0]) {
35
      return;
36
    }
37
    if (isValid(statements, goodPeople, currentPerson)) {
38
      maximumGood(statements, goodPeople, currentPerson + 1, currentGoodPeople + 1, result);
39
    }
40

41
    // Scenario 2: Assume the current person is bad and verify it.
42
    goodPeople[currentPerson] = false;
43
    // Prune the tree for the same reason mentioned earlier.
44
    if (goodPeople.length - currentPerson - 1 + currentGoodPeople < result[0]) {
45
      return;
46
    }
47
    if (isValid(statements, goodPeople, currentPerson)) {
48
      maximumGood(statements, goodPeople, currentPerson + 1, currentGoodPeople, result);
49
    }
50

51
    return;
52
  }
53

54
  private boolean isValid(int[][] statements, boolean[] goodPeople, int currentPerson) {
55
    // To verify if the current assumption of good/bad people is correct, we need to do 2 things.
56
    // 1. We need to verify the statements from all processed good people. What they said about the
57
    // current person should be correct.
58
    for (int i = 0; i < currentPerson; ++i) {
59
      if (goodPeople[i]) {
60
        if (goodPeople[currentPerson] && statements[i][currentPerson] == 0) {
61
          return false;
62
        }
63
        if (!goodPeople[currentPerson] && statements[i][currentPerson] == 1) {
64
          return false;
65
        }
66
      }
67
    }
68

69
    // 2. We need to verify the statement from the current person if he is good. What he said about
70
    // other people should be correct.
71
    if (goodPeople[currentPerson]) {
72
      for (int i = 0; i < currentPerson; ++i) {
73
        if (goodPeople[i] && statements[currentPerson][i] == 0) return false;
74
        if (!goodPeople[i] && statements[currentPerson][i] == 1) return false;
75
      }
76
    }
77

78
    return true;
79
  }
80
}