Maximum Good People Based on Statements - Practice Coding Problems

Maximum Good People Based on Statements - Problem

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 that represents the statements made by n people about each other. More specifically, statements[i][j] could be one of the following:

0 which represents a statement made by person i that person j is a bad person.
1 which represents a statement made by person i that person j is a good person.
2 represents that no statement is made by person i about person j.

Additionally, no person ever makes a statement about themselves. Formally, we have that statements[i][i] = 2 for all 0 <= i < n.

Return the maximum number of people who can be good based on the statements made by the n people.

Input & Output

Example 1 — Basic Consistency Check

$ Input: statements = [[2,1,2],[1,2,2],[2,2,2]]

› Output: 2

💡 Note: Person 0 says person 1 is good, person 1 says person 0 is good. If both are good, their statements are consistent (good people tell truth). Maximum good people = 2.

Example 2 — Contradictory Statements

$ Input: statements = [[2,0],[0,2]]

› Output: 1

💡 Note: Person 0 says person 1 is bad, person 1 says person 0 is bad. They can't both be good (would contradict each other). Maximum good people = 1.

Example 3 — Single Person

$ Input: statements = [[2]]

› Output: 1

💡 Note: Only one person exists, no statements about others. That person can be good. Maximum good people = 1.

Constraints

n == statements.length == statements[i].length
2 ≤ n ≤ 15
statements[i][j] is either 0, 1, or 2
statements[i][i] == 2

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D array where statements[i][j] represents person i's claim about person j

Try Combinations

Test different subsets of people as 'good' (truth-tellers)

Validate Consistency

Check if good people's statements match the assumed reality

Key Takeaway

🎯 Key Insight: Good people always tell the truth, so we find the largest group where everyone's statements are consistent with reality

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that good people always tell the truth, so we need to find the largest subset where all good people's statements are consistent with reality. The best approach uses bit manipulation enumeration to try all 2^n possible combinations of good/bad people and validate consistency. Time: O(n² × 2^n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(2^n)	O(n)	Use backtracking to explore valid combinations more efficiently with early pruning
Try All Combinations	O(n × 2^n)	O(1)	Test every possible subset of people as good and validate consistency

Backtracking with Pruning — Algorithm Steps

Start with empty assignment
For each person, try assigning them as good or bad
Check consistency after each assignment
Prune branches that become invalid early

Visualization

Tap to expand

Step-by-Step Walkthrough

Decision Tree

Each level decides if person i is good or bad

Early Pruning

Stop exploring when inconsistency detected

Track Maximum

Keep track of largest valid assignment found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxGood = 0;

int isValid(int** statements, int* assignment, int personCount, int n) {
    for (int i = 0; i < personCount; i++) {
        if (assignment[i] == 1) { // If person i is good
            for (int j = 0; j < personCount; j++) {
                if (statements[i][j] != 2) { // If i made statement about j
                    int expected = assignment[j];
                    int actual = statements[i][j];
                    if (expected != actual) {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}

void backtrack(int** statements, int* assignment, int personIdx, int n) {
    if (personIdx == n) {
        int goodCount = 0;
        for (int i = 0; i < n; i++) goodCount += assignment[i];
        if (goodCount > maxGood) {
            maxGood = goodCount;
        }
        return;
    }
    
    // Try assigning current person as bad (0)
    assignment[personIdx] = 0;
    if (isValid(statements, assignment, personIdx + 1, n)) {
        backtrack(statements, assignment, personIdx + 1, n);
    }
    
    // Try assigning current person as good (1)
    assignment[personIdx] = 1;
    if (isValid(statements, assignment, personIdx + 1, n)) {
        backtrack(statements, assignment, personIdx + 1, n);
    }
}

int solution(int** statements, int n) {
    maxGood = 0;
    int assignment[15];
    backtrack(statements, assignment, 0, n);
    return maxGood;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    int statements[15][15];
    int n = 0;
    
    // Count rows
    for (int i = 0; input[i]; i++) {
        if (input[i] == '[' && (i == 0 || input[i-1] == ',')) {
            n++;
        }
    }
    n--;
    
    // Parse matrix
    char* ptr = input + 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            statements[i][j] = *ptr - '0';
            ptr += 2;
        }
        ptr++;
    }
    
    int* stmtPtrs[15];
    for (int i = 0; i < n; i++) {
        stmtPtrs[i] = statements[i];
    }
    
    int result = solution(stmtPtrs, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Still explores up to 2^n combinations but with pruning

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth of n for backtracking

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler