Find the Town Judge
Problem Statementβ
Problem Descriptionβ
In a town, there are n
people labeled from 1
to n
. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
- The town judge trusts nobody.
- Everybody (except for the town judge) trusts the town judge.
- There is exactly one person that satisfies properties 1 and 2.
You are given an array trust
where trust[i] = [a_i, b_i]
representing that the person labeled a_i
trusts the person labeled b_i
. If a trust relationship does not exist in trust
array, then such a trust relationship does not exist.
Return the label of the town judge if the town judge exists and can be identified, or return -1
otherwise.
Exampleβ
Example 1:
Input: n = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
Constraintsβ
trust[i].length == 2
- All the pairs of trust are unique.
Solutionβ
Intuitionβ
To identify the town judge, we can use an array to keep track of the trust scores for each person. The trust score is increased by 1 for each person who trusts them and decreased by 1 for each person they trust.
The town judge should have a trust score of n-1
because they are trusted by everyone except themselves and they trust nobody.
Time Complexity and Space Complexity Analysisβ
- Time Complexity: , where is the number of people and is the number of trust relationships.
- Space Complexity: , for the trust score array.
Codeβ
C++β
class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> trustScores(n + 1, 0);
for (const auto& t : trust) {
trustScores[t[0]]--;
trustScores[t[1]]++;
}
for (int i = 1; i <= n; ++i) {
if (trustScores[i] == n - 1) {
return i;
}
}
return -1;
}
};
Pythonβ
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
trust_scores = [0] * (n + 1)
for a, b in trust:
trust_scores[a] -= 1
trust_scores[b] += 1
for i in range(1, n + 1):
if trust_scores[i] == n - 1:
return i
return -1
Javaβ
class Solution {
public int findJudge(int n, int[][] trust) {
int[] trustScores = new int[n + 1];
for (int[] t : trust) {
trustScores[t[0]]--;
trustScores[t[1]]++;
}
for (int i = 1; i <= n; i++) {
if (trustScores[i] == n - 1) {
return i;
}
}
return -1;
}
}