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 <stdio.h>
2#include <stdlib.h>
3
4int findJudge(int n, int** trust, int trustSize, int* trustColSize) {
5 int* inDegrees = (int*)calloc(n + 1, sizeof(int));
6 int* outDegrees = (int*)calloc(n + 1, sizeof(int));
7
8 for (int i = 0; i < trustSize; i++) {
9 int a = trust[i][0];
10 int b = trust[i][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 free(inDegrees);
18 free(outDegrees);
19 return i;
20 }
21 }
22
23 free(inDegrees);
24 free(outDegrees);
25 return -1;
26}
27This C program uses two arrays to store in-degrees and out-degrees of each person. It then iterates through the trust array to update these values accordingly. Finally, it searches for a person whose in-degree is n-1 and out-degree is 0, identifying them as the judge if they exist.
JavaScript solution with a netTrust array identifying the judge by finding the person with net trust equal to n-1.