Sale: Get 60% Off on all Pro Plans. Buy Now

Find the Town Judge

Easy Graph Properties

Problem

Given an integer n representing the number of people in a town labeled from 1 to n, and an array trust where trust[i] = [a, b] indicates that person a trusts person b, return the label of the town judge if they exist and can be identified, or -1 otherwise. The town judge is trusted by everyone else (n - 1 people) and trusts nobody.

  • 1 ≤ n ≤ 1000
  • 0 ≤ trust.length ≤ 10⁴
  • trust[i].length == 2
  • All trust[i] are unique
  • trust[i][0] != trust[i][1]
  • 1 ≤ trust[i][0], trust[i][1] ≤ n

Example

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

Person 3 is trusted by persons 1 and 2, and trusts nobody. The algorithm initializes a score array of length n+1 with zeros. For each trust pair, it decrements the score of the trusting person and increments the score of the trusted person. After processing all pairs, the judge will have a score of n - 1 (trusted by everyone else, trusts no one). Iterating through the scores, the algorithm finds person 3 with score 2 (3 - 1), confirming them as the judge.

Approach

Straightforward Solution

A brute-force approach would check for each person if everyone else trusts them and if they trust no one, resulting in O(n^2) time complexity, which is inefficient for large n.

Core Observation

The town judge is trusted by everyone else (n - 1 people) and trusts no one. This means the judge's net trust score (trusted count minus trusting count) equals n - 1.

Path to Optimal

Preview

Instead of checking trust relationships repeatedly, maintain a score array where each person's score is incremented when trusted and decremented when they trust someone…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a score array of size n+1 with zeros. For each trust pair [a, b], decrement score[a] and increment score[b]…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + trust.length)

The algorithm iterates once over the trust list to update scores and once over the score array to find the judge, each operation linear in input size.

Space

O(n)

The score array uses O(n) auxiliary space proportional to the number of people, which is necessary to track trust relationships efficiently.

Pattern Spotlight

Hash Maps (or Counting Arrays) for Frequency Tracking

Transform relational constraints into net scores by incrementing for incoming trust and decrementing for outgoing trust, enabling O(n) identification of a unique candidate.

Solution

Python
1class Solution:
2 def findJudge(self, n: int, trust: List[List[int]]) -> int:
3 score = [0] * (n + 1)
4
5 for a, b in trust:
6 score[a] -= 1
7 score[b] += 1
8
9 for i in range(1, n + 1):
10 if score[i] == n - 1:
11 return i
12
13 return -1

Step-by-Step Solution

1

Compute Net Trust Scores for All Individuals

3score = [0] * (n + 1)
5for a, b in trust:
6 score[a] -= 1
7 score[b] += 1

Objective

To calculate each person's net trust score by incrementing for being trusted and decrementing for trusting others.

Key Insight

By representing trust relationships as increments and decrements in a single score array, the problem reduces to identifying the person with a net score of n - 1. This approach avoids expensive pairwise checks and leverages simple arithmetic to encode complex relational data.

Interview Quick-Check

Core Logic

Each trust pair updates the score array by decrementing the trusting person's score and incrementing the trusted person's score, capturing the net trust balance.

State & Boundaries

The score array is sized n+1 to align person labels with indices, simplifying indexing and avoiding off-by-one errors.

Common Pitfalls & Bugs

Forgetting to decrement the trusting person's score or increment the trusted person's score breaks the net trust calculation, leading to incorrect judge identification.

2

Identify the Town Judge by Score Matching

To find the person whose net trust score equals n - 1, indicating they are trusted by everyone else and trust no one.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical 
score = [0] * (n + 1)

Initialize a score array of size n+1 with zeros to track net trust scores.

Using an array indexed by person labels allows constant-time updates and lookups, enabling efficient aggregation of trust relationships.

Line 5 Critical 
for a, b in trust:

Iterate over each trust pair [a, b] in the trust list.

Processing each trust relationship once ensures the algorithm runs in linear time relative to the input size.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does the judge's score equal n - 1 after processing all trust pairs?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find the Town Judge from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find the Town Judge drill

or drill a free problem