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.
1#include <vector>
2using namespace std;
3
4int findJudge(int n, vector<vector<int>>& trust) {
5 vector<int> inDegrees(n + 1, 0);
6 vector<int> outDegrees(n + 1, 0);
7
8 for (auto& relation : trust) {
9 int a = relation[0];
10 int b = relation[1];
11 outDegrees[a]++;
12 inDegrees[b]++;
13 }
14
15 for (int i = 1; i <= n; i++) {
16 if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
17 return i;
18 }
19 }
20 return -1;
21}
22This C++ solution uses vectors to track the number of people each individual person trusts and how many people trust them. It traverses the list of trust relations and returns the person that matches the criteria for a town judge.
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.