Find the Town Judge
A town has n people, numbered 1 to n. Exactly one of them may be the town judge. The judge trusts nobody , and everybody else trusts the judge . You are given a list of trust pairs, where [a, b] means person a trusts person b. Return the number of the judge, or -1 if there is no such person. Give every person a score : subtract one each time they trust someone, add one each time someone trusts them. The judge is the only person whose score can reach n - 1.
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ trust.length ≤ 104
- Every trust pair holds two different people
- All trust pairs are different from each other
Example
n = 4, trust = [[1, 3], [1, 4], [2, 3], [2, 4], [4, 3]]3Explanation Person 3 trusts nobody, and persons 1, 2 and 4 all trust person 3. That is n - 1 = 3 people trusting them, so person 3 is the judge.
In plain terms
- Directed edge
- A one-way connection. Here [a, b] points from a to b: a trusts b, but that says nothing about whether b trusts a.
- Out-degree
- How many arrows leave a node. The judge trusts nobody, so the judge has an out-degree of zero.
- In-degree
- How many arrows point at a node. Everyone else trusts the judge, so the judge has an in-degree of n - 1.
- Score
- In-degree minus out-degree, kept in one number per person. Only the judge can end on n - 1.
One cell per person, value = that person’s score so far
Four people, all scores start at zero.
What happens in this step
n = 4 trust = [[1, 3], [1, 4], [2, 3], [2, 4], [4, 3]] score = 0 for persons 1, 2, 3 and 4 A judge would need a score of n - 1 = 3.
Steps to visualize
- The row has one cell per person. The label is the person number and the value is their running score.
- Start every score at zero.
- For each trust pair [a, b], take one away from a and add one to b.
- When every pair has been read, look for a person whose score is exactly n - 1.
- If nobody has that score, there is no judge and the answer is -1.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Four people, all scores start at zero.
What happens in this step
n = 4 trust = [[1, 3], [1, 4], [2, 3], [2, 4], [4, 3]] score = 0 for persons 1, 2, 3 and 4 A judge would need a score of n - 1 = 3.
Solution
function findJudge(n, trust) {
const score = new Array(n + 1).fill(0);
for (const pair of trust) {
score[pair[0]] -= 1;
score[pair[1]] += 1;
}
for (let person = 1; person <= n; person++) {
if (score[person] === n - 1) {
return person;
}
}
return -1;
}- Time
- O(n + t), where t is the number of trust pairs
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 4, trust = [[1, 3], [1, 4], [2, 3], [2, 4], [4, 3]] | 3 | example from the docstring |
n = 2, trust = [[1, 2]] | 2 | smallest town with an actual judge |
n = 3, trust = [[1, 3], [2, 3]] | 3 | both other people trust the same person |
n = 3, trust = [[1, 3], [2, 3], [3, 1]] | -1 | the popular person trusts somebody, so there is no judge |
n = 1, trust = [] | 1 | one person and no trust pairs at all |
n = 3, trust = [[1, 2], [2, 3]] | -1 | a chain of trust with no single trusted person |