Find the Town Judge LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Google
Arista Arista NetworksViews 1649

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.

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.

Examples:

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

Approach for Find The Town Judge:

Idea:

We will be finding the person who trusts no one and is trusted by everyone. For this, we will use an array to store the count of people. For every element of trust, we will increment for trust[0] and will decrement for trust[1].

The idea is that in the end, the judge will be that guy whose count value will be equal to n-1 as everyone would be trusting him and he trust ain’t no one. This means that its count value would have been incremented n-1 times and decremented 0 times, with the final count as n-1.

We will iterate over the count array and will check for the index whose count value is n-1 and will return that index. If we don’t find any index with this value of count, then we will simply return -1.

Code:

Find The Town Judge C++ Leetcode Solution:

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        int trust_count[n];
        memset(trust_count,0,sizeof(trust_count));
        
        for(auto it:trust){
            trust_count[it[0]-1]--;
            trust_count[it[1]-1]++;
        }
        
        for(int i=0;i<n;i++){
            if(trust_count[i]==n-1)
                return i+1;
        }
        return -1;
    }
};

Find The Town Judge Python Leetcode Solution:

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

Complexity Analysis of Find the Town Judge LeetCode Solution:

  • Time Complexity: The time complexity of the above code is O(n),  where n = the number of people.
  • Space Complexity: The space complexity of the above code is O(n).
Translate »