**Problem Statement:**

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

**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

**Solution:**

**Algorithm:**

- Create two arrays inDegree and outDegree.
- Traverse the trust array and update the inDegree and outDegree arrays.
- Traverse the inDegree array and check if the current person is the town judge.
- If the current person is the town judge, return the current person.
- If the town judge does not exist, return -1.

**Code:**

```
public class Solution {
public int findJudge(int n, int[][] trust) {
int[] inDegree = new int[n + 1];
int[] outDegree = new int[n + 1];
for (int[] t : trust) {
outDegree[t[0]]++;
inDegree[t[1]]++;
}
for (int i = 1; i <= n; i++) {
if (inDegree[i] == n - 1 && outDegree[i] == 0) {
return i;
}
}
return -1;
}
}
```

**Time Complexity:**

O(n)O(n) The time complexity is linear, because we traverse the trust array once.

**Space Complexity:**

O(n)O(n) The space complexity is linear, because we create two arrays of size n+1.

## Top comments (0)