Find the Town Judge

Problem

In a town, there are 'n' people labelled from 1 to 'n'. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

The given input is an array of pairs trust[i] = [a, b] representing that the person labelled 'a' trusts the person labelled 'b'.

If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return '-1'.

Solution

To solve the problem we can use a simple array of size N+1 (we will use N+1 to avoid maintaining numbers as arrays starts with index 0 and we have people numbered from 1). Every index starting one represent a member of the town.

We can use following logic to solve the problem.

Lets go through the entire list of trust values and do following things

1. For every 'a' we can reduce -1 in the trust score to mark it not a judge
2. For every 'b' we can add 1 in the trust score to find a person who has maximum score

After going through the list of trusts we need to go through the trust score once again to find an entry for which the score is n-1. If anyone has that score he will be the judge because he is trusted by everyone except himself otherwise return -1 as there is no one trusted by everyone except himself.