# [#997 Graph: Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/)
###### tags:`Graph` `Easy`
<br>
## Issue
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] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
### Example 1
```
Input: n = 2, trust = [[1,2]]
Output: 2
```
### Example 2
```
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
```
### Example 3
```
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
```
### Constraints:
* 1 <= n <= 1000
* 0 <= trust.length <= 104
* trust[i].length == 2
* All the pairs of trust are unique.
* ai != bi
* 1 <= ai, bi <= n
:::danger
Please mind the case when n = 1
:::
### Optimal Space & Time Complexity
:::spoiler Answer
* Time complexity: O(N) where N stands for N people
* Space complexity: O(N) where N stands for N people
:::
<br>
## Solutions
### Most votes
:::spoiler Solution
<br />
[[C++/Java/Python3/Javascript] Everything you need to know from start to end](https://leetcode.com/problems/find-the-town-judge/discuss/1663344/C%2B%2BJavaPython3Javascript-Everything-you-need-to-know-from-start-to-end-.)
```javascript=
var findJudge = function(n, trust) {
const Trusted = new Array(n+1).fill(0);
for(let [i,j] of trust) {
Trusted[i] -= 1
Trusted[j] += 1
}
for(let i = 1; i < Trusted.length; i++) {
if ((n-1) === Trusted[i]) {
return i;
}
}
return -1
};
```
:::
### Everyone's
:::spoiler 東
```javascript=
/*
Graph with adjacency list
Time O(n^2) | Space (n^2) - n is the number of person in village
*/
var findJudge = function(n, trust) {
const trustList = {};
for(const [personLabel, trustedPersonLabel] of trust){
if(!(personLabel in trustList)){
trustList[personLabel] = [trustedPersonLabel]
} else {
trustList[personLabel].push(trustedPersonLabel);
}
}
let possibleJudge = -1;
for(let person = 1; person <= n; person ++){
if(!(person in trustList)){
possibleJudge = person;
for(let otherPerson = 1; otherPerson <= n; otherPerson++){
if(otherPerson !== possibleJudge){
if(!trustList[otherPerson] || !trustList[otherPerson].includes(possibleJudge)){
possibleJudge = -1;
break;
}
}
}
if(possibleJudge !== -1){
return possibleJudge;
}
}
}
return possibleJudge;
};
```
<br>
```javascript
/*
Graph with matrix
Time O(n^2) | Space O(n^2) - n is the number of person in village
*/
var findJudge = function(n, trust) {
const trustMatrix = new Array(n).fill().map(() => new Array(n).fill(0));
for(const [person, trustedPerson] of trust){
trustMatrix[person-1][trustedPerson-1] = 1;
}
for(let person = 1; person <= n; person++){
let possibleJudge = person;
for(let other = 1; other <= n; other++){
if(other !== person &&
(trustMatrix[person-1][other-1] !== 0
|| trustMatrix[other-1][person-1] !== 1)){
possibleJudge = -1;
break;
}
}
if(possibleJudge !== -1) return possibleJudge;
}
return -1;
};
```
<br>
```javascript
/*
Calculation of amount of people one trust and being trusted
Time O(m) | Space O(n) - m is the length of trust array, n is the number of person in village
*/
var findJudge = function(n, trust) {
const trustRecord = new Array(n+1).fill().map(() => new Array(2).fill(0));
for(const [person, trustedPerson] of trust){
trustRecord[person][0] += 1;
trustRecord[trustedPerson][1] += 1;
}
for(let person = 1; person <= n; person ++){
const [trustCnt, beTrustedCnt] = trustRecord[person];
if(trustCnt === 0 && beTrustedCnt === n - 1) return person;
}
return -1;
};
```
:::
<br>
:::spoiler Hao
<br />
It seems little verbose the way to deal with case when `n = 1` here.
```javascript=
/**
* Time complexity: O(N) where N stands for N people
* Space complexity: O(N) where N stands for N people
*/
var findJudge = function(n, trust) {
if (n === 1) return 1;
else {
const judgeCandidates = {};
trust.forEach(([a, whoATrust]) => {
if (judgeCandidates[whoATrust] === undefined) judgeCandidates[whoATrust] = 1;
else if (judgeCandidates[whoATrust] > 0) judgeCandidates[whoATrust] += 1;
judgeCandidates[a] = -1;
});
for (let key in judgeCandidates) {
if (judgeCandidates[key] === n - 1) return key;
};
return -1;
}
};
```
:::
<br>
:::spoiler YC
```javascript=
var findJudge = function(n, trust) {
/*
time: O(n) - where n is the total number of people living in the town
space: O(n) - where n is the total number of people living in the town
*/
const trusted = new Array(n+1).fill(0);
for (let [trustor,trustee] of trust) {
trusted[trustor]--;
trusted[trustee]++;
}
for (let i = 1; i <= n; i++) {
if (trusted[i] === n-1) {
return i;
}
}
return -1;
};
```
:::
<br>
:::spoiler Becky
```javascript=
```
:::
<br>
:::spoiler 月薪
```javascript=
// Time: O(n), Space O(n)
var findJudge = function(n, trust) {
if(n === 1 && trust.length === 0) return n;
const map = { candidates: [], trusts: [] };
trust.forEach((i) => {
const truster = i[0], trustee = i[1];
map.trusts.push(truster);
if(trustee in map){
map[trustee] += 1;
}else{
map[trustee] = 1;
}
if(map[trustee] === n - 1){
map.candidates.push(trustee);
}
})
if(map.candidates.length === 1){
for(let v of map.trusts){
if(map.candidates[0] === v) return -1
}
return map.candidates[0]
}
return -1
};
```
:::
<br>
## Discussion
### Why is this leetcode related to `graph`?
### Is the most efficient time complexity O(N) or O(M), which N stands for the number of people in town nd M stands for the length of array 'trust'
Sign in with Wallet
Connect another wallet