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)