Degree characterization
Treat each trust pair [a, b] as a directed edge from person a to person b. A town judge trusts nobody, so their outdegree is 0. Everyone else trusts the judge, so their indegree is n - 1. Both conditions are necessary: an incoming-edge count alone could identify someone who also trusts another person.
Count incoming and outgoing edges for every person, then return the person satisfying both conditions. For n == 1, the sole person has indegree and outdegree zero; they meet the conditions precisely when there are no trust edges, so the same scan handles this edge case without a special branch. If nobody meets both conditions, return -1.
Each trust pair is processed once and each person is checked once, giving O(n + m) time for m = trust.length. The two degree arrays use O(n) extra space.
class Solution {
public int findJudge(int n, int[][] trust) {
int[] indegree = new int[n + 1];
int[] outdegree = new int[n + 1];
for (int[] relation : trust) {
outdegree[relation[0]]++;
indegree[relation[1]]++;
}
for (int person = 1; person <= n; person++) {
if (outdegree[person] == 0 && indegree[person] == n - 1) {
return person;
}
}
return -1;
}
}