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
This Python function counts the number of people each individual trusts and the number of people who trust them using two separate lists. It then searches for a person who is trusted by n-1 others while trusting no one.
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 <stdio.h>
2#include <stdlib.h>
3
4int findJudge(int n, int** trust, int trustSize, int* trustColSize) {
5 int* netTrust = (int*)calloc(n + 1, sizeof(int));
6
7 for (int i = 0; i < trustSize; i++) {
8 int a = trust[i][0];
9 int b = trust[i][1];
10 netTrust[a]--;
11 netTrust[b]++;
12 }
13
14 for (int i = 1; i <= n; i++) {
15 if (netTrust[i] == n - 1) {
16 free(netTrust);
17 return i;
18 }
19 }
20
21 free(netTrust);
22 return -1;
23}
24This C implementation uses a single array to track the net trust value of each person. A candidate judge should have a net positive trust equal to n-1.