Find the Town Judge

1. Define the problem

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 ≤ 10⁴
Every trust pair holds two different people
All trust pairs are different from each other

Example

Inputn = 4, trust = [[1, 3], [1, 4], [2, 3], [2, 4], [4, 3]]

Output3

Explanation 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.

2. Know the words first

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.

3. Visualize the solution

One cell per person, value = that person’s score so far

Statusinit

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.

Step 1 of 6

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.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per person, value = that person’s score so far

Statusinit

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.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

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)

6. Test cases

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

Find the Town Judge