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.
1var findJudge = function(n, trust) {
2 const inDegrees = new Array(n + 1).fill(0);
3 const outDegrees = new Array(n + 1).fill(0);
4
5 for (const [a, b] of trust) {
6 outDegrees[a]++;
7 inDegrees[b]++;
8 }
9
10 for (let i = 1; i <= n; i++) {
11 if (inDegrees[i] === n - 1 && outDegrees[i] === 0) {
12 return i;
13 }
14 }
15 return -1;
16};
17In JavaScript, we use arrays to compute in-degrees and out-degrees and then check each person to see if they could be the town judge by meeting the conditions.
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)
1#include <vector>
2using namespace std;
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> netTrust(n + 1, 0);
for (auto& t : 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 an array to calculate net trust for each person. If a person has a net trust value of n-1, they are the judge.