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

1. The number of people who trust judge can only be n - 1
2. 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.