What pattern does Find the Town Judge use?

The Pattern: Hash Maps (or Counting Arrays) for Frequency Tracking The Heuristic: Transform relational constraints into net scores by incrementing for incoming trust and decrementing for outgoing trust, enabling O(n) identification of a unique candidate.

Find the Town Judge - LeetCode Solution

Q: What is the time complexity of Find the Town Judge?

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.

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

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. This transforms the problem into a single pass over the trust list and a final pass over the scores, reducing time complexity to O(n + trust.length).

Optimal Approach

Initialize a score array of size n+1 with zeros. For each trust pair [a, b], decrement score[a] and increment score[b]. After processing, the judge is the person with score equal to n - 1. Return that person's label or -1 if none found.

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.

Solution

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

9for i in range(1, n + 1):
10    if score[i] == n - 1:
11        return i
13return -1

Objective

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

Key Insight

After computing net trust scores, the judge is uniquely identified by having a score of n - 1. Iterating through the scores from 1 to n ensures the correct person is found efficiently. Returning -1 if no such person exists handles cases where the judge does not exist.

Interview Quick-Check

Core Logic

The judge must have a score of exactly n - 1, reflecting trust from all others and no outgoing trust.

State & Boundaries

Iterate from 1 to n because person labels start at 1, ensuring correct mapping between scores and individuals.

Common Pitfalls & Bugs

Returning -1 if no score matches n - 1 is essential to correctly indicate the absence of a judge.

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.

Line 6 Standard

score[a] -= 1

Decrement the score of the trusting person a.

Decrementing the trusting person's score encodes the fact that they trust someone else, which disqualifies them from being the judge.

Line 7 Standard

score[b] += 1

Increment the score of the trusted person b.

Incrementing the trusted person's score reflects that they are trusted by someone, increasing their likelihood of being the judge.

Line 9 Standard

for i in range(1, n + 1):

Iterate through all people from 1 to n to find the judge.

Checking each person's score ensures that the unique judge, if any, is identified by their net trust score.

Line 10 Standard

if score[i] == n - 1:

Check if the current person's score equals n - 1.

A score of n - 1 means the person is trusted by everyone else and trusts no one, satisfying the judge conditions.

Line 11 Standard

return i

Return the label of the person identified as the judge.

Returning immediately upon finding the judge optimizes runtime by avoiding unnecessary checks.

Line 13 Standard

return -1

Return -1 if no judge is found after checking all people.

Returning -1 correctly signals that no person meets the judge criteria, handling edge cases.

Test Your Understanding

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

Because the judge is trusted by all other n - 1 people (each incrementing their score) and trusts no one (no decrements), resulting in a net score of n - 1.

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

1	`class 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`

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

9	`for i in range(1, n + 1):`
10	`if score[i] == n - 1:`
11	`return i`
13	`return -1`