# LeetCode 997: Find the Town Judge

## Problem Restatement

There are `n` people in a town labeled from `1` to `n`.

We are given an array `trust`, where each pair:

```python
[a, b]
```

means person `a` trusts person `b`.

We need to find the town judge.

If the judge exists, then:

| Rule | Meaning |
|---|---|
| Trusts nobody | The judge has no outgoing trust |
| Trusted by everyone else | Exactly `n - 1` people trust the judge |
| Unique | There is exactly one person satisfying both rules |

If no judge can be identified, return `-1`.

The official constraints include `1 <= n <= 1000`, `0 <= trust.length <= 10^4`, all trust pairs are unique, and `a != b`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` and trust pairs `trust` |
| Output | Label of the town judge, or `-1` |
| People labels | `1` through `n` |
| Trust direction | `[a, b]` means `a` trusts `b` |

Function shape:

```python
def findJudge(n: int, trust: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

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

Person `1` trusts person `2`.

Person `2` trusts nobody.

Everyone except person `2` trusts person `2`.

Answer:

```python
2
```

Example 2:

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

Persons `1` and `2` both trust person `3`.

Person `3` trusts nobody.

Answer:

```python
3
```

Example 3:

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

Person `3` is trusted by `1` and `2`, but person `3` trusts person `1`.

So person `3` cannot be the judge.

Answer:

```python
-1
```

## First Thought: Check Each Person

A direct solution is to test every person as a judge candidate.

For a candidate `person`, check all trust pairs:

1. If `person` appears as the first value, then they trust someone, so they cannot be judge.
2. Count how many people trust `person`.
3. If that count is `n - 1`, then `person` is the judge.

```python
class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        for person in range(1, n + 1):
            trusts_someone = False
            trusted_by = 0

            for a, b in trust:
                if a == person:
                    trusts_someone = True
                    break

                if b == person:
                    trusted_by += 1

            if not trusts_someone and trusted_by == n - 1:
                return person

        return -1
```

This works, but it repeats the same scan for every person.

## Problem With Repeated Scanning

If there are `n` people and `m` trust pairs, the direct solution costs:

```python
O(n * m)
```

We can do better by counting incoming and outgoing trust once.

## Key Insight

The town judge has a very specific graph shape.

| Count | Judge requirement |
|---|---|
| Outgoing trust count | `0` |
| Incoming trust count | `n - 1` |

For each pair `[a, b]`:

```python
a trusts b
```

So:

```python
outgoing[a] += 1
incoming[b] += 1
```

After processing all pairs, the judge is the person whose outgoing count is `0` and incoming count is `n - 1`.

## Algorithm

Create two arrays of size `n + 1`:

```python
incoming
outgoing
```

Then process every pair `[a, b]`:

1. Increment `outgoing[a]`.
2. Increment `incoming[b]`.

Then scan people from `1` to `n`.

Return the person `i` such that:

```python
outgoing[i] == 0 and incoming[i] == n - 1
```

If no such person exists, return `-1`.

## Correctness

For each trust pair `[a, b]`, the algorithm records one outgoing trust for `a` and one incoming trust for `b`.

Therefore, after all pairs are processed, `outgoing[i]` is exactly the number of people that person `i` trusts, and `incoming[i]` is exactly the number of people who trust person `i`.

A town judge must trust nobody, so their outgoing count must be `0`.

A town judge must be trusted by everybody else, so their incoming count must be `n - 1`.

The algorithm checks exactly these two conditions for every person. If it returns a person, that person satisfies the definition of town judge. If no person satisfies both conditions, no town judge exists.

## Complexity

Let `m = len(trust)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + m)` | Process all trust pairs once, then scan all people once |
| Space | `O(n)` | Store incoming and outgoing counts |

## Implementation

```python
class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        incoming = [0] * (n + 1)
        outgoing = [0] * (n + 1)

        for a, b in trust:
            outgoing[a] += 1
            incoming[b] += 1

        for person in range(1, n + 1):
            if outgoing[person] == 0 and incoming[person] == n - 1:
                return person

        return -1
```

## Code Explanation

We create arrays indexed by person label:

```python
incoming = [0] * (n + 1)
outgoing = [0] * (n + 1)
```

Index `0` is unused because people are labeled from `1` to `n`.

For every trust pair:

```python
for a, b in trust:
```

person `a` trusts someone:

```python
outgoing[a] += 1
```

person `b` is trusted by someone:

```python
incoming[b] += 1
```

Then we check every person:

```python
for person in range(1, n + 1):
```

The judge must satisfy both count conditions:

```python
if outgoing[person] == 0 and incoming[person] == n - 1:
```

If no person satisfies them, return `-1`.

## Alternative: One Score Array

We can combine incoming and outgoing counts into one score.

For each trust pair `[a, b]`:

```python
score[a] -= 1
score[b] += 1
```

The judge has score `n - 1`, because they receive trust from `n - 1` people and give trust to nobody.

```python
class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        score = [0] * (n + 1)

        for a, b in trust:
            score[a] -= 1
            score[b] += 1

        for person in range(1, n + 1):
            if score[person] == n - 1:
                return person

        return -1
```

This has the same time and space complexity, but uses one array instead of two.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findJudge(2, [[1, 2]]) == 2
    assert s.findJudge(3, [[1, 3], [2, 3]]) == 3
    assert s.findJudge(3, [[1, 3], [2, 3], [3, 1]]) == -1
    assert s.findJudge(1, []) == 1
    assert s.findJudge(4, [[1, 3], [2, 3], [4, 3]]) == 3
    assert s.findJudge(3, []) == -1

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| `2`, `[[1,2]]` | `2` | One person trusts the judge |
| `3`, `[[1,3],[2,3]]` | `3` | Everyone else trusts `3` |
| `3`, `[[1,3],[2,3],[3,1]]` | `-1` | Candidate trusts someone |
| `1`, `[]` | `1` | Single person trusts nobody and needs no incoming trust |
| `4`, `[[1,3],[2,3],[4,3]]` | `3` | Judge trusted by all other people |
| `3`, `[]` | `-1` | No one is trusted by `n - 1` people |