Skip to content

997. Find the Town Judge

On LeetCode ->

Problem

Given people labeled 1 through n and directed trust relationships, return the unique person who:

  • Trusts nobody.
  • Is trusted by every other person.

Return -1 if no such person exists.

n = 3, trust = [[1, 3], [2, 3]]
degrees: 1 -> (in=0, out=1), 2 -> (in=0, out=1), 3 -> (in=2, out=0)
output: 3

Key trick

Track indegree - outdegree: the judge gains 1 from each of the other n - 1 people and loses nothing, so their score is exactly n - 1.

Trap

  • The required indegree is n - 1, not n.
  • A candidate with indegree n - 1 is invalid if they trust anyone.
  • For n = 1 with no relationships, person 1 is the judge.

Why is it interesting?

It reduces two graph-degree conditions to one score per vertex, avoiding an explicit graph representation.

Python solution

class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        score = [0] * (n + 1)

        for a, b in trust:
            # Trusting someone counts against being the judge;
            # being trusted counts toward being the judge.
            score[a] -= 1
            score[b] += 1

        for person in range(1, n + 1):
            if score[person] == n - 1:
                return person

        return -1

Time complexity: \(O(n + |\text{trust}|)\).

Space complexity: \(O(n)\).

Comment on my solution

  • The implementation is correct, including the n = 1 case.
  • The idea comment incorrectly says the judge's indegree is n; it must be n - 1.
  • Separate indegree and outdegree arrays are clear, but one net-score array makes the solution shorter.
  • Building two candidate lists adds unnecessary passes and allocations.

Your solution has time complexity \(O(n + |\text{trust}|)\) and space complexity \(O(n)\).

# Ideas:
# - if a judge x exist:
#   - indegree[x] == n
#   - outegree[x] == 0
#   - and no other y satify above constraints

# WORKS
class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        indegree = [0] * n
        outdegree = [0] * n
        for a, b in trust:
            indegree[b - 1] += 1
            outdegree[a - 1] += 1
        indegree_n = [i + 1 for i, k in enumerate(indegree) if k == n - 1]
        outdegree_0 = [i + 1 for i, k in enumerate(outdegree) if k == 0]
        if len(indegree_n) == 1 and len(outdegree_0) == 1 and indegree_n[0] == outdegree_0[0]:
            return indegree_n[0]
        else:
            return -1