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. If there is a town judge, they must meet these conditions:

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:

• The judge doesn’t trust anyone.

• Everyone else (except the judge) trusts the judge.

• Only one person in the town can meet both of these conditions.

Given there is n and a two-dimensional array called trust,  each element trust[i] has two elements $[a_i,b_i]$, it means that a trusts person b. If there is a judge, return their number, return $-1$ otherwise.

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: