Find the Town Judge

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

 

Note:

1. 1 <= N <= 1000
2. trust.length <= 10000
3. trust[i] are all different
4. trust[i][0] != trust[i][1]
5. 1 <= trust[i][0], trust[i][1] <= N

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

Try it on Leetcode

Here, consider trust as a pairs of directed graph. i.e., indegree - outdegree = N-1 will become judge.

Iterate all trust and count all degree. [i.e., if trust(a, b) occurs then decrease trust[a] and increase trust[b]].

Finally check out for judge condition and returns result.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation


Please let us know your views in comment section

Subscribe us to receive updates instantly..

Happy Coding..!!