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 Sam K., 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

More Graphs practice problems

See all Graphs problems →