How do you approach Find the Town Judge?

Track in-degree minus out-degree for each person.

What are common mistakes on Find the Town Judge?

Building the adjacency list in one direction on an undirected graph. Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest. Ignoring self-loops and parallel edges when the constraints allow them.

gitGood.dev

← Back to problems

Find the Town Judge

MediumAlgorithms

Description

In a town of `n` people labeled `1` to `n`, there may be a **town judge**. The judge trusts nobody, everybody (except the judge) trusts the judge, and there is exactly one such person. Given `trust` where `trust[i] = [a, b]` means person `a` trusts person `b`, return the judge's label, or `-1` if there is no judge.

Example 1

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

Output: 2

Explanation: Person 2 is trusted by 1 and trusts no one.

Example 2

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

Output: -1

Explanation: Person 3 trusts someone, so cannot be the judge.

Constraints

- 1 <= n <= 1000 - 0 <= trust.length <= 10^4 - All trust pairs are unique

Find the Town Judge: approach, complexity and pitfalls

A medium graphs problem, graded against 4 test cases (2 of them hidden).

The pattern: Graphs

Nodes and edges - traversal, connectivity, cycles, and shortest paths.

Reach for it when you see: Explicit edges, a grid treated as a graph, or dependencies between items.

More Graphsproblems →

If you are stuck

Show the 2-step hint ladder

Track in-degree minus out-degree for each person.
The judge is the unique person whose net trust score equals n - 1.

The optimal approach

Show the approach: The approach

Degree counting. For each trust pair, decrement the truster's score and increment the trustee's. The judge is trusted by everyone else (+(n-1)) and trusts no one (0 out), so the judge is the person whose score equals `n - 1`.

Time: O(n + trust). Space: O(n).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Graphs mistakes

These apply to the pattern as a whole, not just this problem.

Building the adjacency list in one direction on an undirected graph.
Assuming the graph is connected. Most inputs allow several components, and one traversal from node 0 misses the rest.
Ignoring self-loops and parallel edges when the constraints allow them.