A town judge lacks even self-trust. So, in the trust graph, the town judge looks like a sink: in-degree = n-1 and out-degree = 0. And, there must be exactly one such sink vertex.
Time: 
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
out_degree = {u: 0 for u in range(1, n + 1)}
in_degree = {u: 0 for u in range(1, n + 1)}
for u, v in trust:
out_degree[u] += 1
in_degree[v] += 1
candidates = [
u for u in range(1, n + 1) if out_degree[u] == 0 and in_degree[u] == n - 1
]
return candidates[0] if len(candidates) == 1 else -1
More concisely, we can define trustworthiness of a person as (indegree-outdegree). Then, a person with trustworthiness = n-1 is a candidate for town judge.
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
trustworthiness = [0] * (n+1)
for u, v in trust:
trustworthiness[u] -= 1
trustworthiness[v] += 1
candidate_judges = [u for u in range(1, n+1) if trustworthiness[u] == n-1]
return candidate_judges[0] if len(candidate_judges) == 1 else -1
unreasonably effective 
Leave a comment