💬 Discord
Sign In
NeetCode #558LC-997EasyGraphsNC 250
← Back to All Problems

#558 · #997 · Find the Town Judge(找到小镇的法官)

📌 Problem Statement & Constraints

In a town of n people labelled 1..n, trust[i] = [a, b] means person a trusts person b. The judge trusts nobody, and everybody else trusts the judge. Return the judge's label, or -1. Constraints: 1 <= n <= 1000, 0 <= trust.length <= 10^4.

💡 Core Algorithmic Approaches

  1. Track an in-degree and out-degree per person.
  2. The judge has in-degree n - 1 (everyone trusts them) and out-degree 0 (trusts nobody).
  3. So a single pass over the trust pairs suffices, followed by a scan for the qualifying person.
  4. Equivalently, compute score[i] = in_degree - out_degree and find the person with score n - 1.

💻 Benchmark Python3 Implementation

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indeg = [0] * (n + 1)
        outdeg = [0] * (n + 1)
        for a, b in trust:
            outdeg[a] += 1                 # a trusts someone
            indeg[b] += 1                  # b is trusted
        for i in range(1, n + 1):
            if indeg[i] == n - 1 and outdeg[i] == 0:
                return i
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + E): one pass over the trust pairs and one over the people.
💾 Space Complexity
O(n) for the two degree arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Only checking the in-degree: the judge must also trust nobody, so the out-degree must be 0.
  • Requiring in-degree n: a person cannot trust themselves, so the maximum is n - 1.
  • Using 0-indexed arrays without care: the labels are 1..n.
  • Assuming the judge exists: return -1 otherwise.