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.
Java solution making use of a net trust array. The judge should have a net trust value of n-1 since they trust no one but everyone else trusts them.