Skip to main content

997. Find the Town Judge

easy

In a town of n people, the judge trusts nobody but is trusted by everyone else. Given a list of trust pairs, return the judge's label or -1. A clean in-degree minus out-degree trick on a directed graph.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

In a town, there are n people labeled 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, and there is exactly one person that satisfies properties 1 and 2. You are given an array trust where trust[i] = [ai, bi] representing that ai trusts bi. Return the label of the town judge if they exist, otherwise return -1.

Constraints

  • 1 <= n <= 1000
  • 0 <= trust.length <= 10^4
  • trust[i].length == 2
  • All the pairs of trust are unique.
  • ai != bi
  • 1 <= ai, bi <= n

Examples

Example 1

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

Explanation: Person 1 trusts person 2 and person 2 trusts nobody — person 2 is the judge.

Example 2

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

Example 3

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

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Model people as nodes and 'a trusts b' as a directed edge a -> b. What in-degree and out-degree pattern does the judge satisfy?

Hint 2

The judge has in-degree n-1 (everyone else trusts them) and out-degree 0 (they trust nobody).

Hint 3

Maintain a single score array: increment score[b] and decrement score[a] for each pair. The judge's score is exactly n-1.

Solution approach

Reveal approach

Treat trust as a directed graph edge a -> b. The judge is the unique node with in-degree n-1 and out-degree 0. Instead of two arrays, collapse to one: for each pair [a, b] do score[b] += 1 and score[a] -= 1. The judge's final score is (n-1) - 0 = n-1. Scan score[1..n] and return any node whose score equals n-1; otherwise return -1. The uniqueness guarantee in the problem statement means there's at most one such node, so we don't need a tiebreak. O(E + n) time, O(n) space.

Complexity

Time
O(E + n)
Space
O(n)

Related patterns

  • graph
  • in-degree
  • counting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Find the Town Judge and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →