Graph Theory37 sections · 1633 units
Open in Course

Town Judge - The Algorithm

How to solve it

I'll show you how to find the town judge using degree counting. The judge must be trusted by everyone, so in-degree equals n1n-1. The judge trusts nobody, so out-degree equals 00.

You loop through all people and check if anyone satisfies both conditions. If yes, return that person. If no, return 1-1.

Time complexity: O(n+t)O(n + t) where tt is the number of trust pairs. Space complexity: O(n)O(n) for the degree arrays.