Find the Town Judge
In a town, there are N people labelled 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 these conditions. You are given an array trust where trust[i] = [a, b] representing that the person labelled a trusts the person labelled b. Return the label of the town judge if the town judge exists and can be identified, or return -1.
Constraints:
- 1 <= N <= 1000
- 0 <= trust.length <= 1000
- trust[i].length == 2
- All the pairs of trust are unique.
Examples:
Input: [2, [[1,2]]]
Output: 2
Explanation: The person labelled 2 has no one they trust, and the person labelled 1 trusts them.
Solutions
Graph Approach
We create an array trustCount of size N + 1 to keep track of the trust count for each person. We iterate through the trust array and for each pair [a, b], we decrement the trust count of person a and increment the trust count of person b. Then we iterate through the trustCount array and return the index i if the trust count is equal to N - 1, which means person i is the town judge. If no such person is found, we return -1.
public int findJudge(int N, int[][] trust) {
int[] trustCount = new int[N + 1];
for (int[] t : trust) {
trustCount[t[0]]--;
trustCount[t[1]]++;
}
for (int i = 1;
i <= N;
i++) {
if (trustCount[i] == N - 1) return i;
}
return -1;
}Follow-up:
What if there are multiple town judges?
