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.
Python solution with a single net trust list updating trust values. Only a judge will have a net trust of n-1, indicating they are trusted by all other citizens.