There are n people labeled 1..n and a list trust where [a, b] means person a trusts person b. The town judge trusts nobody, and everybody else trusts the judge. Return the judge's label, or -1 if there is none.
Give each person a single score: add 1 when someone trusts them, subtract 1 when they trust someone. The judge is the only person who can reach exactly n - 1, because they collect a trust from all n - 1 others and never lose a point.
def findJudge(n, trust):
score = [0] * (n + 1)
for a, b in trust:
score[a] -= 1
score[b] += 1
for person in range(1, n + 1):
if score[person] == n - 1:
return person
return -1
O(n + t) time for t trust pairs and O(n) extra space.
Start with the two-array version (in-degree and out-degree), then point out that the judge needs in-degree n - 1 and out-degree 0, so one combined number is enough. Mention the edge case n = 1 with no trust pairs: the single person is the judge, and the loop handles it because n - 1 = 0.
I work on Linkjob AI. If you want practice explaining graph problems like this out loud, an AI tool for job interviews can help you rehearse.
Further reading: Linkjob AI resource directory