Find the Town Judge

Problem Statement

In a small town, each of the n residents is assigned a unique number from 1 to n. Amidst these residents, it's rumored that there is one particular individual who is the town judge. The special attributes of the town judge, according to the rumor, are that the judge trusts nobody, but they’re trusted by every other townsperson. Additionally, only one person in the town exhibits this behavior.

To programmatically determine if such a town judge exists, and if so, identify them, we are provided with a list known as trust. This list contains pairs [ai, bi], indicating that person ai trusts person bi. If there's no entry for a person in the form [x, bi], it means x trusts no one. Conversely, if there's no entry in the form [ai, x], then x is trusted by none.

The challenge is to process the trust list and output the label of the town judge if they exist based on the above criteria. If no such person meets the criteria, the function should return -1.

Examples

Example 1

Input:

n = 2, trust = [[1,2]]

Output:

2

Explanation:

Person 1 trusts person 2. Person 2 trusts nobody.
Person 2 is trusted by one person (n-1 = 1) and trusts no one → judge = 2.

Example 2

Input:

n = 3, trust = [[1,3],[2,3]]

Output:

3

Explanation:

Persons 1 and 2 both trust person 3.
Person 3 trusts no one and is trusted by two others (n-1 = 2) → judge = 3.

Example 3

Input:

n = 3, trust = [[1,3],[2,3],[3,1]]

Output:

-1

Explanation:

Person 3 trusts person 1 → disqualified from being the judge (they trust someone).

Constraints

• 1 <= n <= 1000
• 0 <= trust.length <= 10^4
• trust[i].length == 2
• All the pairs of trust are unique
• ai != bi
• 1 <= ai, bi <= n

Approach and Intuition

Intuition

The town judge, if they exist, must:

1. Be trusted by exactly n - 1 people.
2. Trust no one.

This dual requirement gives us a simple and effective pattern to check.

Approach

1. Initialization:

   • Create an array trust_count of size n+1 initialized to zero.

     • trust_count[i] will track the net trust score of person i.
     • Every time someone trusts person i, we increment trust_count[i].
     • Every time person i trusts someone, we decrement trust_count[i].

2. Process the Trust List:

   • For each pair [a, b] in trust:

     • Decrease trust_count[a] (a trusts someone).
     • Increase trust_count[b] (b is trusted by someone).

3. Find the Judge:

   • Loop through 1 to n:

     • If trust_count[i] == n - 1, return i as the town judge.

   • If no such person exists, return -1.

This logic ensures:

• A person with a net score of n-1 is trusted by everyone else and trusts no one.

This approach runs in O(n + m) time where m is the number of trust entries — suitable given the constraints.

Solutions

public int identifyJudge(int total, int[][] trustings) {
    
    if (trustings.length < total - 1) {
        return -1;
    }
    
    int[] trustCounts = new int[total + 1];

    for (int[] trustPair : trustings) {
        trustCounts[trustPair[0]]--;
        trustCounts[trustPair[1]]++;
    }
    
    for (int person = 1; person <= total; person++) {
        if (trustCounts[person] == total - 1) {
            return person;
        }
    }
    return -1;
}