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.
JavaScript solution with a netTrust array identifying the judge by finding the person with net trust equal to n-1.