Leetcode 997. Find the Town Judge
Problem Explanation:
In the given problem, you are required to identify the town judge if one exists. The town judge is the person that meets the following conditions: they trust nobody, and everybody else in the town trusts them.
The trust relations are represented by an array of pairs trust[i] = [a, b]
implies that person a trusts person b.
The task is to determine the label of the town judge if one exists. If no town judge exists, you are required to return -1.
For example, in a town of two people labelled 1 and 2 represented by N = 2
and trust relation given bytrust = [[1, 2]]
implies that person 1 trusts person 2 but person 2 trusts no one. So, person 2 fulfills both conditions of being the judge hence, the output should be 2.
Solution Approach:
The solution uses the count array method to keep track of trust relationships. The count of each person is represented by an array where count[i] is initially 0 for all i. If a person is trusted by another person, its count is increased by 1 and if a person trusts someone else, its count is decreased by 1.
The town judge should be trusted by everyone else and not trust anyone else. Therefore, the town judge should have a count of n - 1 in the trust array.
Only one person will have a count of n - 1 and doesn't trust anyone else. If one such person doesn't exist or there are more than one such people, then the town does not have a judge.
Example:
Taking a town of three people as an example with N=3
and trust = [[1,3],[2,3]]
, initial count of all people as count = [0,0,0,0]
,
1The first pair in trust array is [1,3] which decreases count[1] by 1 and increases count[3] by 1, resulting to `count = [0,-1,0,1]`, 2 3The second pair decreases count[2] by 1 and increases count[3] by 1 resulting to `count = [0,-1,-1,2]`, 4 5No more trust pairs. Now, the person trusted by everyone and does not trust anyone (count = n-1) is person 3.
Solution in Python:
1 2python 3class Solution: 4 def findJudge(self, N: int, trust: List[List[int]]) -> int: 5 # Create a count list of N+1 elements, all are 0 6 count = [0] * (N+1) 7 # Iterate over each pair in trust list 8 for i, j in trust: 9 # Decrease the count of the person i who trusts another. 10 count[i] -= 1 11 # Increase the count of the person j who is trusted by another. 12 count[j] += 1 13 # Iterate over each person 14 for i in range(1, N+1): 15 # If a person is trusted by everyone and doesn't trust anyone, return that person. 16 if count[i] == N - 1: 17 return i 18 return -1
Solution in Java:
1
2java
3class Solution {
4 public int findJudge(int N, int[][] trust) {
5 int[] count = new int[N+1];
6 for (int[] t : trust) {
7 count[t[0]]--;
8 count[t[1]]++;
9 }
10 for (int i = 1; i <= N; ++i) {
11 if (count[i] == N - 1) {
12 return i;
13 }
14 }
15 return -1;
16 }
17}
Solution in JavaScript:
1 2Javasript 3var findJudge = function(N, trust) { 4 let trustCounts=new Array(N+1).fill(0) 5 6 for(let relation of trust){ 7 trustCounts[relation[0]]--; 8 trustCounts[relation[1]]++; 9 } 10 for(let i = 1; i <= N; i++){ 11 if(trustCounts[i]==N-1) 12 return i; 13 } 14 return -1 15};
Solution in C++:
1
2C++
3class Solution {
4public:
5 int findJudge(int N, vector<vector<int>>& trust) {
6 vector<int> counts(N+1,0);
7 for(auto& t:trust){
8 counts[t[0]]--;
9 counts[t[1]]++;
10 }
11 for(int i=1; i<=N; i++){
12 if(counts[i]==N-1)
13 return i;
14 }
15 return -1;
16 }
17};
Solution in C#:
1
2C#
3public class Solution {
4 public int FindJudge(int N, int[][] trust) {
5 int[] counts = new int[N+1];
6 foreach(int[] t in trust){
7 counts[t[0]]--;
8 counts[t[1]]++;
9 }
10 for(int i=1; i<=N; i++){
11 if(counts[i]==N-1)
12 return i;
13 }
14 return -1;
15 }
16}
In all above solutions, firstly an array for trust count count
is initialized. Then for each trust relation, count of trusting person is decreased and the count of trusted person is increased. And at the end, the person having count
equal to N-1
is the town judge. If no such person found then return -1 representing no judge in town.# Time Complexity:
The time complexity of the solution is O(T + N), where T is the total number of trust relations and N is the number of people in the town. This is because the solution needs to iterate over the trust array to count the trust scores for each person, and then iterate over the counts array to identify the town judge.
Space Complexity:
The space complexity of the solution is O(N), where N is the number of people in the town. This is because the solution requires a counts array to keep track of the trust scores for each person.
Conclusion:
The solution efficiently identifies the town judge, if one exists, by calculating trust scores for each person using a counts array. The town judge is the person with a trust score of N - 1. The solution handles all edge cases: when there is no town judge, it returns -1. The implementation of the logic is direct and straightforward in Python, Java, JavaScript, C++ and C#.
However, it is necessary to validate the inputs to the function, especially in languages like JavaScript, to prevent potential run-time errors. Overall, this problem is a good introduction to the use of trust scores or counts and their application in identifying unique or outlier entities in a set.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.