Find The Town Judge - Leetcode Solution

Problem statement: 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.

You are given trust, 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.

Example 1:

Input: N = 2, trust = [[1,2]] Output: 2

Example 2:

Input: N = 3, trust = [[1,3],[2,3]] Output: 3

Example 3:

Input: N = 3, trust = [[1,3],[2,3],[3,1]] Output: -1

Example 4:

Input: N = 3, trust = [[1,2],[2,3]] Output: -1

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]] Output: 3

Solution:

The first solution that comes to mind is to represent the trust relationship of the people in form of a directed graph. Each person will be a node in the graph and an edge from node u to node v will represent that u trusts v.

We will maintain 2 arrays:

1. trusts_count: The number of people who trust a person.
2. is_trusted_by_count: The number of people that a person is trusted by.

Initially, trusts_count will be set to 0 for all people and is_trusted_by_count will be set to 0 for all people except the town judge (if the town judge exists). We can calculate the value of is_trusted_by_count for each person by iterating over all the trust relationships and incrementing the count of the person being trusted.

Next, we will traverse the trust array and for each relationship trust[u][v], we will increment the trusts_count[v] by 1.

After calculating trusts_count and is_trusted_by_count we need to find a person who trusts nobody (i.e., trusts_count[i] == 0) but is trusted by everyone else (i.e., is_trusted_by_count[i] == N-1).

If we find such a person then that is the town judge, and we return his label i. If we don't find such a person, then the town judge does not exist and we return -1.

Let's see the implementation of the above algorithm:

function findJudge(N, trust) { let is_trusted_by_count = new Array(N+1).fill(0); let trusts_count = new Array(N+1).fill(0);

for(let i=0;i<trust.length;i++){ let u = trust[i][0]; let v = trust[i][1]; is_trusted_by_count[v]++; trusts_count[u]++; }

for(let i=1;i<=N;i++){ if(trusts_count[i] == 0 && is_trusted_by_count[i] == N-1) return i; }

return -1; }

Time Complexity: O(N+M), where N is the number of people, and M is the number of trust relationships.

Space Complexity: O(N), since we are maintaining 2 arrays of size N.

1