Solution For Find The Town Judge

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.

Step by Step Implementation For Find The Town Judge

class Solution {
    public int findJudge(int N, int[][] trust) {
        // create an array of size N + 1 to store the count
        // of people each person trusts
        int[] count = new int[N+1];
        
        // create an array of size N + 1 to store the count
        // of people that trust each person
        int[] trusted = new int[N+1];
        
        // iterate through the trust array and update the count
        // and trusted arrays
        for (int i = 0; i < trust.length; i++) {
            count[trust[i][0]]++;
            trusted[trust[i][1]]++;
        }
        
        // iterate through the count and trusted arrays to find
        // the index of the judge
        for (int i = 1; i <= N; i++) {
            // the judge must be trusted by everyone and must not trust anyone
            if (trusted[i] == N - 1 && count[i] == 0) {
                return i;
            }
        }
        
        // if no judge is found, return -1
        return -1;
    }
}

def findJudge(N, trust):
    
    # initialize list of size N+1 with all zeros
    # list at index i corresponds to person i
    # list[i] will keep track of the number of people person i trusts
    trusts_list = [0] * (N+1)
    
    # initialize list of size N+1 with all zeros
    # list at index i corresponds to person i
    # list[i] will keep track of the number of people who trust person i
    trusted_by_list = [0] * (N+1)
    
    # loop through each trust relationship and update the corresponding
    # values in the trusts_list and trusted_by_list
    for i in range(len(trust)):
        trusts_list[trust[i][0]] += 1
        trusted_by_list[trust[i][1]] += 1
    
    # loop through each person and check if they are the judge
    # the judge must have a trusts_list[i] value of 0 (meaning they don't trust anyone)
    # and a trusted_by_list[i] value of N-1 (meaning everyone else trusts them)
    for i in range(1, N+1):
        if trusts_list[i] == 0 and trusted_by_list[i] == N-1:
            return i
    
    # if no one meets the criteria of being the judge, return -1
    return -1

var findJudge = function(N, trust) {
    
    // create a map to store the number of people each person trusts
    let map = new Map();
    
    // create a map to store the number of people each person is trusted by
    let reverseMap = new Map();
    
    // fill out both maps
    for (let i = 0; i < trust.length; i++) {
        let a = trust[i][0];
        let b = trust[i][1];
        
        if (!map.has(a)) {
            map.set(a, [b]);
        } else {
            let curr = map.get(a);
            curr.push(b);
            map.set(a, curr);
        }
        
        if (!reverseMap.has(b)) {
            reverseMap.set(b, [a]);
        } else {
            let curr = reverseMap.get(b);
            curr.push(a);
            reverseMap.set(b, curr);
        }
    }
    
    // check if there is only one person who is trusted by everyone and doesn't trust anyone
    for (let key of reverseMap.keys()) {
        if (reverseMap.get(key).length == N - 1 && !map.has(key)) {
            return key;
        }
    }
    
    return -1;
};

class Solution {
public:
    int findJudge(int N, vector>& trust) {
        // vector inDegree(N+1, 0);
        // vector outDegree(N+1, 0);
        int inDegree[N+1] = {0};
        int outDegree[N+1] = {0};
        for(auto& t: trust){
            outDegree[t[0]]++;
            inDegree[t[1]]++;
        }
        for(int i = 1; i <= N; i++){
            if(outDegree[i] == 0 && inDegree[i] == N-1) return i;
        }
        return -1;
    }
};

public class Solution {
    public int FindJudge(int N, int[][] trust) {
        if (trust.Length == 0)
        {
            return N;
        }
        
        var map = new Dictionary>();
        
        foreach (var t in trust)
        {
            if (!map.ContainsKey(t[0]))
            {
                map.Add(t[0], new HashSet());
            }
            
            map[t[0]].Add(t[1]);
        }
        
        for (int i = 1; i <= N; i++)
        {
            if (!map.ContainsKey(i))
            {
                int count = 0;
                
                foreach (var kvp in map)
                {
                    if (kvp.Value.Contains(i))
                    {
                        count++;
                    }
                }
                
                if (count == N - 1)
                {
                    return i;
                }
            }
        }
        
        return -1;
    }
}