Sponsored
Sponsored
The idea is to calculate the in-degree and out-degree for each person. A person is the town judge if their in-degree is n-1 (trusted by all other n-1 people) and their out-degree is 0 (trusting no one).
Time Complexity: O(trust.length), where trust.length is the total number of trust relationships.
Space Complexity: O(n), where n is the number of people in the town.
1public class Solution {
2 public int FindJudge(int n, int[][] trust) {
3 int[] inDegrees = new int[n + 1];
4 int[] outDegrees = new int[n + 1];
5
6 foreach (var t in trust) {
7 int a = t[0], b = t[1];
8 outDegrees[a]++;
9 inDegrees[b]++;
10 }
11
12 for (int i = 1; i <= n; i++) {
13 if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
14 return i;
15 }
16 }
17 return -1;
18 }
19}
20The C# implementation uses arrays to store the in-degree and out-degree of every person based on the trust relationships. It then iterates to find the potential town judge based on the required properties.
An alternative approach is to use a single array to calculate the difference between in-degrees and out-degrees. For the judge, this difference should be n-1.
Time Complexity: O(trust.length)
Space Complexity: O(n)
1public class Solution {
2 public int FindJudge(int n, int[][] trust) {
int[] netTrust = new int[n + 1];
foreach (var t in trust) {
int a = t[0], b = t[1];
netTrust[a]--;
netTrust[b]++;
}
for (int i = 1; i <= n; i++) {
if (netTrust[i] == n - 1) {
return i;
}
}
return -1;
}
}
C# solution using a single array to compute net trust levels. The judge is identified by having a net trust level of n-1.