Find the Town Judge

Difficulty: Easy | Acceptance: 50.70% | Paid: No Topics: Array, Hash Table, Graph Theory

In a town, there are n people labeled from 1 to n. One of these people is the town judge.

The town judge trusts nobody. Everybody (except for the town judge) trusts the town judge. There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labeled a trusts the person labeled b.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

• Examples
• Constraints
• Brute Force Simulation
• Graph Indegree/Outdegree
• Single Array Score

Examples

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints

1 <= n <= 1000
0 <= trust.length <= 10⁴
trust[i].length == 2
0 <= ai, bi <= n
ai != bi

Brute Force Simulation

Intuition We can check every person from 1 to n to see if they meet the criteria of being a judge. For each candidate, we scan the entire trust list to verify they trust no one and everyone else trusts them.

Steps

• Iterate through each person i from 1 to n.
• Assume i is the judge. Check if i appears as the first element (truster) in any pair. If yes, i is disqualified.
• Check if every other person j (where j != i) appears as the first element in a pair where i is the second element (trusted).
• If both conditions are met, return i.
• If the loop finishes without finding a judge, return -1.

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        for i in range(1, n + 1):
            trusts_someone = False
            for a, b in trust:
                if a == i:
                    trusts_someone = True
                    break
            if trusts_someone:
                continue
            
            trusted_by_all = True
            for j in range(1, n + 1):
                if i == j:
                    continue
                found = False
                for a, b in trust:
                    if a == j and b == i:
                        found = True
                        break
                if not found:
                    trusted_by_all = False
                    break
            
            if trusted_by_all:
                return i
        return -1

Complexity

• Time: O(n² + n·E) where E is the length of trust. In the worst case, for each person, we scan the trust list multiple times.
• Space: O(1)
• Notes: Simple to understand but inefficient for large inputs.

Graph Indegree/Outdegree

Intuition Model the problem as a directed graph. An edge a -> b means a trusts b. The judge must have an indegree of n-1 (trusted by everyone else) and an outdegree of 0 (trusts nobody).

Steps

• Initialize two arrays, inDegree and outDegree, of size n+1 with zeros.
• Iterate through the trust array. For each pair [a, b], increment outDegree[a] and increment inDegree[b].
• Iterate from 1 to n. If a person i has inDegree[i] == n-1 and outDegree[i] == 0, return i.
• If no such person is found, return -1.

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if n == 1:
            return 1
        
        in_degree = [0] * (n + 1)
        out_degree = [0] * (n + 1)
        
        for a, b in trust:
            out_degree[a] += 1
            in_degree[b] += 1
            
        for i in range(1, n + 1):
            if in_degree[i] == n - 1 and out_degree[i] == 0:
                return i
                
        return -1

Complexity

• Time: O(n + E) where E is the length of the trust array.
• Space: O(n) to store the degree arrays.
• Notes: Efficient and standard graph traversal approach.

Single Array Score

Intuition We can optimize space by using a single array to track the “trust score”. If a trusts b, we decrement a’s score (since they trust someone) and increment b’s score (since they are trusted). The judge will end up with a score of n-1 (trusted by n-1 people, trusts 0).

Steps

• Initialize a score array of size n+1 with zeros.
• Iterate through trust. For each pair [a, b], decrement score[a] and increment score[b].
• Iterate from 1 to n. If score[i] == n-1, return i.
• Return -1 if no judge is found.

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        score = [0] * (n + 1)
        
        for a, b in trust:
            score[a] -= 1
            score[b] += 1
            
        for i in range(1, n + 1):
            if score[i] == n - 1:
                return i
                
        return -1

Complexity

• Time: O(n + E)
• Space: O(n)
• Notes: Optimal solution with reduced constant factors compared to using two arrays.