Find the Town Judge LeetCode Solution

Problem Statement:

Find the Town Judge LeetCode Solution – 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 and we need to find 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] = [a_i, b_i] representing that the person labeled a_i trust the person labeled b_i.

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

Algorithm –

IDEA –

In order to find the solution to find the town judge, what we will do in this question is, we have to focus on the judge(the judge doesn’t trust anyone and everybody trusts the town judge). So there are n people including the town judge and we have a 2d array so the first person of each element trusts the second person so we will focus on the count of every element(range between 1 to N)  if the count of the element will be equal to N-1 that person will be a town judge.

Approach –

• first, create one array of length(n+1).
• increase the count if the element is placed in the second column of each row(it doesn’t trust anybody) and increase the count of the array[element].
•  decrease the count if the element is placed in the first column of each row(it trusts anyone) and decrease the count of array[element].
• then check for the count if the count is equal to n-1 return that index of the array.
• else return -1.
• Hence, we are now able to find the town judge

Find The Town Judge Leetcode Python Solution:

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        
        if n == 1:
            return 1
        
        new_ar = [0]*(n+1)
        for i in range(len(trust)):
            
            new_ar[trust[i][0]] -= 1
            new_ar[trust[i][1]] += 1
            
        print(new_ar)
        for i in range(len(new_ar)):
            if new_ar[i] == n-1:
                return i
            
        return -1    

Find The Town Judge Leetcode Java Solution:

class Solution {
    public int findJudge(int n, int[][] trust) {
        int new_ar[] = new int[n+1];
        
        for(int t[] : trust){
            new_ar[t[0]]--;     
            new_ar[t[1]]++;   
        }
        
        for(int i=1;i<=n;i++){
            if(new_ar[i]==n-1) return i;
        }
        
        return -1;
        
    }
}
        

Time Complexity

The Time Complexity of the above solution is O(len(trust)).

Space Complexity:

The Space Complexity of the above solution is O(N).