Domain 1EasyCORE

Find the Town Judge

The problem involves identifying a town judge in a town with `N` people. The town judge is defined by two properties: 1. The town judge trusts nobody. 2. Everybody (except for the town judge) trusts the town judge.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Graph

997. Find the Town Judge

Model: qwen2.5-coder:14b
Topics: Graph
FAANG asked: 1
Acceptance rate: 49.8%


Problem Breakdown

The problem involves identifying a town judge in a town with N people. The town judge is defined by two properties:

  1. The town judge trusts nobody.
  2. Everybody (except for the town judge) trusts the town judge.

We are given an array of trust pairs, where each pair [a, b] indicates that person a trusts person b. We need to determine if there exists a town judge and return their label. If no such person exists, we return -1.

Inputs:

  • N: An integer representing the number of people in the town.
  • trust: A list of trust pairs.

Outputs:

  • An integer representing the label of the town judge or -1 if no such person exists.

Implicit Constraints/Edge Cases:

  • If N = 1, there is only one person, who by default could be considered the town judge unless there are trust relationships.
  • If trust is empty and N > 1, it’s impossible for a town judge to exist because no one trusts anyone else.

Intuition

A brute-force approach would involve checking each person to see if they meet the criteria of being trusted by everyone else and trusting nobody. This approach would have a time complexity of O(N^2) due to nested loops, which is inefficient given the constraints.

The key insight is to use an array to keep track of trust counts for each person:

  • Increment the count for people who are trusted.
  • Decrement the count for people who trust others.
  • The town judge will be the person with a count equal to N - 1 (trusted by everyone else) and not trusting anyone.

This approach reduces the time complexity to O(N + T), where T is the number of trust relationships, making it more efficient.

Approach

  1. Initialize an array trust_counts of size N + 1 to keep track of trust counts for each person (index represents the person).
  2. Iterate through the trust list:
    • For each pair [a, b], decrement trust_counts[a] because a trusts someone.
    • Increment trust_counts[b] because b is trusted by someone.
  3. After processing all trust relationships, iterate through the trust_counts array to find a person with a count of N - 1.
  4. If such a person exists, return their label; otherwise, return -1.

Complexity Analysis

  • Time Complexity: O(N + T), where N is the number of people and T is the number of trust relationships.
  • Space Complexity: O(N) for storing the trust_counts array.

Solution

def findJudge(N, trust):
    if N == 1:
        return 1 if not trust else -1
    
    trust_counts = [0] * (N + 1)
    
    for a, b in trust:
        trust_counts[a] -= 1
        trust_counts[b] += 1
    
    for i in range(1, N + 1):
        if trust_counts[i] == N - 1:
            return i
    
    return -1

Edge Cases Handled

  • Single Person (N = 1): If there’s only one person and no trust relationships, they are the judge. Otherwise, no judge exists.
  • No Trust Relationships: If trust is empty and N > 1, no judge can exist because no one trusts anyone else.
  • Multiple People Trusting Each Other: The algorithm correctly identifies the town judge even if multiple people trust each other, as long as one person meets the criteria of being trusted by everyone else and trusting nobody.