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

**Example 4:**

Input:n = 3, trust = [[1,2],[2,3]]Output:-1

**Example 5:**

Input:n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]Output:3

**Constraints:**

`1 <= n <= 1000`

`0 <= trust.length <= 10^4`

`trust[i].length == 2`

- All the pairs of
`trust`

are**unique**. `ai != bi`

`1 <= ai, bi <= n`

The description was taken from https://leetcode.com/problems/find-the-town-judge/.

`#O(V+E) Time, O(V+E) Space`

**class** **Solution**:

**def** **findJudge**(self, n: int, trust: List[List[int]]) -> int:

**if** len(trust) < n - **1**:

**return** -**1**

adjacency = collections.defaultdict(list)

seen = collections.defaultdict(int)

**for** node, neighbor **in** trust:

adjacency[node].append(neighbor)

seen[neighbor] += **1**

**for** node **in** range(**1**, n+**1**):

**if** **not** adjacency[node] **and** seen[node] == n-**1**:

**return** node

**return** -**1**

The input is given to us as a list of edges between nodes, a list of trusts between people.

In order to solve this, we can make an adjacency list to create a graph. Once we have done that, we will look for the node that has no child nodes and that has been seen as a child in each other nodes' adjacency list.

If that node doesn't exist, we will return a negative one.

Starting off, if the edges list is less than the number of nodes minus one, then each node can't be connected. A graph with three nodes would have two edges to connect them, for example.

If that is the case, we will return a negative one because the judge would need to have a connection with everybody else.

` `

**if** len(trust) < n - **1**:

**return** -**1**

Otherwise, we will create a default dictionary for our adjacency list and our counter of how many times we have seen each neighbor/child node. A normal HashMap dictionary would work as well but we would have to create more boiler plate code for checking if an item exists in these before we call them to avoid errors.

` adjacency = collections.defaultdict(list)`

seen = collections.defaultdict(int)

For each node and neighbor in the trust edges list, we will make a connection from the node to the neighbor in our adjacency list and increment the number of times that we have seen the neighbor.

` `

**for** node, neighbor **in** trust:

adjacency[node].append(neighbor)

seen[neighbor] += **1**

Then, we will traverse each node in an attempt to find the node that has no neighbors that it trusts, and has been seen in the adjacency list of each other node.

If we find it, we will return it.

` `

**for** node **in** range(**1**, n+**1**):

**if** **not** adjacency[node] **and** seen[node] == n-**1**:

**return** node

Otherwise, the node doesn't exist so we will return a negative one.

` `

**return** -**1**