Problem 20.2 · Graph FundamentalsEasy

Find the Town Judge

What it teaches: In-degree and out-degree on a directed graph, computed straight from the edge list.

Practise it on judges as “Find the Town Judge”.

The problem

In a town of n people labelled 1..n, trust[i] = [a, b] means a trusts b. The judge trusts nobody and is trusted by everyone else. Return the judge's label, or −1 if there isn't exactly one.

Example 1

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 2

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Constraints

1 ≤ n ≤ 1000
Pairs are distinct

Pattern clues in the wording

→ "Everyone" and "nobody": in-degree n − 1, out-degree 0

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findJudge(int n, int[][] trust) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 2 trust = [[1,2]]	2
2	n = 3 trust = [[1,3],[2,3]]	3
3	n = 3 trust = [[1,3],[2,3],[3,1]]	-1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Net degree · O(n + T)

Net degree

Time O(n + T) Space O(n)

score[b]++ and score[a]-- for each pair. The judge is the person whose score is n − 1.

▶ Dry run: n = 3, trust = [[1,3],[2,3]]n = 3, trust = [[1,3],[2,3]]

Step 1/2Arrows show who trusts whom.

Approach 1

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] score = new int[n + 1];
        for (int[] t : trust) { score[t[0]]--; score[t[1]]++; }
        for (int p = 1; p <= n; p++) if (score[p] == n - 1) return p;
        return -1;
    }
}

Verdict: One array, one pass.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1 with no trust (the only person is the judge)
Two candidates trusted by many

Mistakes people make

Checking only in-degree (a candidate who also trusts someone isn't the judge).

Interview

Follow-up questions

This is the "celebrity problem". How do you solve it if you can only ask knows(a, b)?

Command Palette

The problem

Approaches

Net degree

Edge cases and common mistakes

Follow-up questions