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:
 The town judge trusts nobody.
 Everybody (except for the town judge) trusts the town judge.
 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.
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 rowwise.
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]==n1){ 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).