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.
1def findJudge(n, trust):
2 in_degrees = [0] * (n + 1)
3 out_degrees = [0] * (n + 1)
4
5 for a, b in trust:
6 out_degrees[a] += 1
7 in_degrees[b] += 1
8
9 for i in range(1, n + 1):
10 if in_degrees[i] == n - 1 and out_degrees[i] == 0:
11 return i
12 return -1
13This 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.
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.