Solution: Find the Town Judge

Statement

There are n people numbered from $1$ to n in a town. There’s a rumor that one of these people is secretly the town judge. A town judge must meet the following conditions:

1. The judge doesn’t trust anyone.

2. Everyone else in the town (except the town judge) trusts the judge.

3. There is exactly one person who fulfills both the above conditions.

You are given an integer n and a two-dimensional array, trust, where each entry $trust[i] = [a_i, b_i]$ indicates that the person labeled $a_i$ trusts the person labeled $b_i$. If a trust relationship is not specified in the trust array, it does not exist. Your task is to determine the label of the town judge, if one can be identified. If no such person exists, return $-1$.

Constraints:

• $1 \leq$n $\leq 1000$

• $0 \leq$trust.length $\leq 10^{4}$

• trust[i].length $== 2$

• ai $\ne$ bi

• $1 \leq$ai , bi $\leq$n

• All the pairs in trust are unique.

Solution

This algorithm to find the town judge is based on the graph representing trust relationships, where each person is a vertex and directed edges show the trust between them. To solve the problem, the algorithm uses two arrays: one for the indegree and another for the outdegree of each person. In graphs, the outdegree of a vertex (person in this case) refers to the connections going out from it (how many people they trust), and the indegree of a vertex refers to connections coming in (how many people trust them).

To find the judge, the algorithm searches for the person whose indegree is exactly n - 1, which indicates that everyone else trusts that person, and whose outdegree is $0$, which indicates that they do not trust anyone. If such a person exists, they are the judge. If no person meets these criteria, the algorithm returns $−1$, which means there is no judge in the town.

The algorithm to solve this problem is as follows:

• If the length of the trust relationship is less than n - 1, it means that not all persons trust someone, we will return -1 in this case.

• Create two arrays indegree and outdegree, to count the indegree and outdegree of a person, respectively:

• Loop through the trust array, which contains pairs $[a, b]$, and for each pair:

  • Increase the outdegree[a] by $1$, because person $a$ is trusts someone.

  • Increase the indegree[b] by $1$, because person $b$ is trusted by someone.

• After processing the trust relationships, iterate over indegree and outdegree arrays and check if a person’s indegree is exactly n - 1, which means all other people trust them. The outdegree of that person should also be exactly $0$, which means that the person does not trust anybody. If such a person is found, we will return its index.

• After the loop terminates, return -1, which indicates that there is no judge.

Let’s look at the following illustration to get a better understanding of the solution: