Easy_Question6 : Find the Town Judge

In a town, there are n people labeled 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 an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

 

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

 

Constraints:

• 1 <= n <= 1000
• 0 <= trust.length <= 104
• trust[i].length == 2
• All the pairs of trust are unique.
• ai != bi
• 1 <= ai, bi <= n

Let’s treat the given scenario as a directed graph in which an edge from person a to b shows that a trusts b.

A town judge does not trust anybody thus, town judge has no outgoing edge. All other n-1 persons trust town judge thus, total n-1 incoming edge towards town judge from all other person.

We can further understand that difference between number of incoming edges and number of outgoing edges is n-1 for town judge only.

If we talk about a simple person then he will surely trust town judge thus min(outgoing edges)=1 and in best case even if all other person trust him(of course town judge won’t trust him) thus max(incoming edges)= n-2.

The maximum difference between incoming and outgoing edges for this person is n-2-(1) = n-3.

Also if there is no town judge then no person can achieve the n-1 difference between a number of incoming and outgoing edges.

Now, our main task is to calculate the difference i.e. number of incoming edges – number of outgoing edges for each person. We will do so by traversing the trust array row-wise.

In any row, there are two elements. Left element is who trusts and right element is whom the left element trusts.

Thus left element has outgoing edge to right element. Hence, difference value for left element will decrease by 1 and for right element, increase by 1.

In our code, we have used netTrustGains array for this task. Each index i of this array shows the difference value for ith person.

After traversing trust array, we will run a loop for each person from 1 to n and check if any person has the difference value = n-1.

If such a person is found then we will return him else we will return -1.

import java.util.*;
import java.lang.*;
public class Solution
{  
    public static void main(String args[])
    {
        int n = 3;
        int[][]trust = {{1,3},{2,3}};
        System.out.println(findJudge(n,trust));
    }
    public static int findJudge(int n, int[][] trust) 
    {
        int[]netTrustGains=new int[n+1];
        for(int[]i:trust){
            netTrustGains[i[0]]--;
            netTrustGains[i[1]]++;
            
        }
        int judge=-1;
        for(int i=1;i<=n;i++){
            if(netTrustGains[i]==n-1){
                judge=i;
            }
        }
        return judge;
    }
}

Complexity Analysis for Find the Town Judge Solution

Time Complexity

O(max(n,trust.size())) : We have traversed the trust loop linearly and another loop is of size n to check the netTrustGains for each person from 1 to n.

Space Complexity 

O(n) : We have created an array netTrustGains of size n+1 thus space complexity O(n).