# Find the Town Judge
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-town-judge)
Canonical: https://scaleengineer.com/dsa/problems/find-the-town-judge
**Data structures:** Array, Hash Table, Graph
**Companies:** [Turing](https://scaleengineer.com/companies/turing), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
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:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. 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`. If a trust relationship does not exist in `trust` array, then such a trust relationship does not exist.

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`

# Approaches
## Brute Force Iteration
This approach involves iterating through each person from 1 to `n` and checking if they meet the criteria of a town judge. For each person, we scan the entire `trust` list to verify the two conditions: they trust no one, and everyone else trusts them.
**Time:** O(N * E), where N is the number of people and E is the number of trust relationships. For each of the N candidates, we iterate through all E relationships. · **Space:** O(1), as we only use a few variables for counting and flags, not dependent on the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient for larger inputs as it repeatedly scans the `trust` array, leading to a high time complexity.
### Explanation
The algorithm considers every person from 1 to `n` as a potential candidate for the town judge. For each candidate `i`, we perform two checks by iterating through the `trust` array:

1.  **Check if `i` trusts anyone:** We scan the `trust` array. If we find an entry `[i, x]`, it means candidate `i` trusts person `x`, violating the first rule. Thus, `i` cannot be the judge, and we move to the next candidate.
2.  **Check if `i` is trusted by everyone else:** We count how many people trust candidate `i`. We iterate through the `trust` array and increment a counter for every entry `[x, i]`.

If a candidate `i` trusts no one (passes check 1) and is trusted by exactly `n-1` people (passes check 2), we have found the judge. Since the problem guarantees at most one judge, we can immediately return `i`. If we check all `n` people and none satisfy both conditions, it means no judge exists, and we return -1.

```java
class Solution {
    public int findJudge(int n, int[][] trust) {
        for (int i = 1; i <= n; i++) {
            int trustedByCount = 0;
            boolean trustsSomeone = false;

            // Check if candidate 'i' trusts anyone
            for (int[] relation : trust) {
                if (relation[0] == i) {
                    trustsSomeone = true;
                    break;
                }
            }

            if (trustsSomeone) {
                continue; // This candidate is disqualified, move to the next
            }

            // Check how many people trust candidate 'i'
            for (int[] relation : trust) {
                if (relation[1] == i) {
                    trustedByCount++;
                }
            }

            // Check if conditions are met
            if (trustedByCount == n - 1) {
                return i; // Found the judge
            }
        }

        return -1; // No judge found
    }
}
```
### Algorithm
- Loop through each person `i` from 1 to `n`, considering them as a potential judge.
- For each candidate `i`, we need to verify two conditions by scanning the entire `trust` array:
  1. **Trusts Nobody**: Check if there is any entry `[i, x]` in the `trust` array. If one is found, `i` cannot be the judge.
  2. **Trusted by Everyone Else**: Count the number of people who trust `i`. This is the number of entries `[x, i]` in the `trust` array.
- If a candidate `i` trusts no one AND is trusted by exactly `n - 1` people, they are the judge. Return `i`.
- If the loop finishes without finding a judge, it means no one satisfies the conditions. Return -1.

## Graph-based Approach with Two Arrays
This approach models the problem as a directed graph where people are nodes and trust relationships are edges. The town judge is a node with an in-degree of `n-1` (is trusted by everyone else) and an out-degree of `0` (trusts nobody). We can calculate these degrees for all people in a single pass over the `trust` array.
**Time:** O(N + E), where N is the number of people and E is the number of trust relationships. We iterate through the `trust` array once (O(E)) and then iterate through the people once (O(N)). · **Space:** O(N), for the two arrays of size `n+1` used to store the in-degrees and out-degrees.
**Pros:** Much more efficient than the brute-force approach with linear time complexity.; The logic directly maps to the graph properties of the judge, making it easy to reason about.
**Cons:** Uses extra space proportional to the number of people, which could be a concern for very large N.
### Explanation
The core idea is to efficiently count the number of people each person trusts (out-degree) and the number of people who trust them (in-degree). Instead of recounting for each candidate, we can pre-calculate these values for everyone.

We use two arrays, `inDegree` and `outDegree`, both of size `n + 1`, initialized to zeros. The extra space is for convenient 1-based indexing.

We iterate through the `trust` array once. For each relationship `[a, b]`:
- `outDegree[a]` is incremented, signifying that person `a` trusts someone.
- `inDegree[b]` is incremented, signifying that person `b` is trusted by someone.

After this single pass, the arrays hold the final degree counts for every person. We then iterate from person 1 to `n` and check for the one who satisfies the judge's properties: `outDegree[i] == 0` and `inDegree[i] == n - 1`. If we find such a person, we return their label. If the loop completes without finding a judge, we return -1.

```java
class Solution {
    public int findJudge(int n, int[][] trust) {
        if (n == 1) {
            return 1;
        }
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];

        for (int[] relation : trust) {
            outDegree[relation[0]]++;
            inDegree[relation[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- Create two integer arrays, `inDegree` and `outDegree`, of size `n + 1`, and initialize them to all zeros.
- Iterate through each relationship `[a, b]` in the `trust` array.
- For each relationship, increment `outDegree[a]` (person `a` trusts someone) and `inDegree[b]` (person `b` is trusted by someone).
- After populating the arrays, iterate from `i = 1` to `n`.
- For each person `i`, check if `inDegree[i] == n - 1` and `outDegree[i] == 0`.
- If both conditions are true, `i` is the judge. Return `i`.
- If the loop completes without finding a judge, return -1.

## Optimized Approach with a Single Array
This is an optimization of the two-array approach. Instead of tracking in-degrees and out-degrees separately, we can use a single array to maintain a "trust score" for each person. A person who trusts someone loses a point, and a person who is trusted gains a point. The judge will be the only person with a final score of `n-1`.
**Time:** O(N + E), where N is the number of people and E is the number of trust relationships. We make one pass over the trust relationships (O(E)) and one pass over the people (O(N)). · **Space:** O(N), for the single array of size `n+1` used to store the trust scores.
**Pros:** Most efficient in terms of time and space (among these three).; The logic is concise and combines two conditions into one check.; Uses half the space of the two-array approach.
**Cons:** The logic of using a single score might be slightly less intuitive at first glance compared to separate in/out degree counts.
### Explanation
This approach refines the degree-counting method by using a single array. The logic is that a town judge must end up with a score of `n - 1`. This is because:
- The judge is trusted by `n - 1` other people, so their score gets incremented `n - 1` times.
- The judge trusts no one, so their score is never decremented.
- Any other person `i` either trusts someone (their score is decremented at least once, so it can't be `n-1`) or is not trusted by everyone (their score won't reach `n-1`).

The algorithm proceeds as follows:
1.  Create a single array, `trustScores`, of size `n + 1`, initialized to zeros.
2.  Iterate through the `trust` array. For each relationship `[a, b]`:
    - Decrement the score of the truster: `trustScores[a]--`.
    - Increment the score of the trustee: `trustScores[b]++`.
3.  After the loop, iterate from person 1 to `n`.
4.  If any person `i` has `trustScores[i] == n - 1`, they are the judge. Return `i`.
5.  If no such person is found, return -1.

This approach is elegant as it combines the two conditions into a single score check.

```java
class Solution {
    public int findJudge(int n, int[][] trust) {
        if (n == 1) {
            return 1;
        }

        int[] trustScores = new int[n + 1];

        for (int[] relation : trust) {
            // Person 'a' trusts someone, their score decreases.
            trustScores[relation[0]]--;

            // Person 'b' is trusted by someone, their score increases.
            trustScores[relation[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            // The judge is trusted by n-1 people and trusts no one.
            if (trustScores[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- Create a single integer array, `trustScores`, of size `n + 1`, initialized to all zeros.
- Iterate through each relationship `[a, b]` in the `trust` array.
- For each relationship, decrement `trustScores[a]` and increment `trustScores[b]`.
- After the loop, iterate from `i = 1` to `n`.
- If `trustScores[i]` is equal to `n - 1`, then person `i` is the judge. Return `i`.
- If the loop finishes and no such person is found, return -1.

# Solutions
### Java

```java
class Solution {
public
  int findJudge(int n, int[][] trust) {
    int[] cnt1 = new int[n + 1];
    int[] cnt2 = new int[n + 1];
    for (var t : trust) {
      int a = t[0], b = t[1];
      ++cnt1[a];
      ++cnt2[b];
    }
    for (int i = 1; i <= n; ++i) {
      if (cnt1[i] == 0 && cnt2[i] == n - 1) {
        return i;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findJudge(int n, vector<vector<int>> &trust) {
    vector<int> cnt1(n + 1);
    vector<int> cnt2(n + 1);
    for (auto &t : trust) {
      int a = t[0], b = t[1];
      ++cnt1[a];
      ++cnt2[b];
    }
    for (int i = 1; i <= n; ++i) {
      if (cnt1[i] == 0 && cnt2[i] == n - 1) {
        return i;
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int: cnt1 = [0] * (n + 1) cnt2 = [0] * (n + 1) for a, b in trust: cnt1[a] += 1 cnt2[b] += 1 for i in range(1, n + 1): if cnt1[i] == 0 and cnt2[i] == n - 1: return i return - 1

```