Photo by James Harrison on Unsplash

# [LeetCode] 997. Find the Town Judge

## Daily LeetCoding Challenge January, Day 3

## Table of contents

This article includes the code implementation in Python, a detailed explanation, and the complexity analysis for LeetCode - 997. Find the Town Judge. Please hit the like button if you find this article is helpful to you. I will keep writing LeetCode solutions.

# Explanation

The criteria to be a judge can be translated into something like

- The number of people who trust judge can only be
`n - 1`

- Judge can only trust
`0`

people

It means if we only need to count if there is a person who has exactly `n - 1`

trust from the others. But how do we know if the person does not trust anyone? It can be achieved by decreasing the count of trusts by `1`

if the person trusts anyone.

Let's take a look at example 3 in the description:

```
n = 3, trust = [[1,3],[2,3],[3,1]]
```

We can initialize the count array as `[0] * (n + 1)`

. (Index 0 is not going to be used since the people label starts from 1. Then we iterate the `trust`

array. )

```
[0, 0, 0, 0]
```

The first subarray is `[1, 3]`

so we need to set `count[1] = count[1] - 1`

because people `1`

trusts someone. And we need to set `count[3] = count[3] + 1`

because people 3 got one trust.

```
[0, -1, 0, 1]
```

The second subarray is `[2, 3]`

so the `count`

array becomes

```
[0, -1, -1, 2]
```

The third subarray is `[3, 1]`

. You may notice that the person with label `3`

trusts the person with label `1`

which makes the people with label `3`

does not the criteria to be a judge. That is why we need to set the `count[3] = count[3] - 1`

so the `count[3]`

is not equal to `n - 1`

after we iterating the `trust`

array. Count array becomes:

```
[0, 0, -1, 1]
```

Hence, nobody meets the criteria to be a judge because nobody's count is equal to

`n - 1 = 2`

# Code Implementation in Python

```
def findJudge(self, n: int, trust: List[List[int]]) -> int:
count = [0] * (n + 1)
# Count the trust
for a, b in trust:
count[a] -= 1
count[b] += 1
# Check if there is a person who has exactly n - 1 trust
for i in range(1, n + 1):
if count[i] == n - 1:
return i
return -1
```

# Complexity Analysis

`O(n) time | O(n) space - where n is the number of people`

We need to iterate the trust array to count the trust so the time complexity is O(n). We need an additional array to store the trust count so the space complexity is O(n) too.