---
# System prepended metadata

title: '[#997 Graph: Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/)'
tags: [Easy, Graph]

---

# [#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'