Problem Description

This problem asks you to identify the "town judge" among n people labeled from 1 to n.

The town judge has two unique characteristics:

1. The judge trusts nobody - they don't trust any other person in the town
2. Everyone else trusts the judge - all other n-1 people trust the judge

You're given an array trust where each element trust[i] = [ai, bi] means person ai trusts person bi. The trust relationships are directional - if person A trusts person B, it doesn't mean B trusts A.

Your task is to find and return the label of the town judge if such a person exists. If no valid judge can be identified, return -1.

For example:

• If n = 3 and trust = [[1,3], [2,3]], person 3 is the judge because:
  • Person 3 trusts nobody (no entries with 3 as the first element)
  • Everyone else (persons 1 and 2) trusts person 3

The solution uses two counting arrays:

• cnt1[i] tracks how many people person i trusts (outgoing trust)
• cnt2[i] tracks how many people trust person i (incoming trust)

A person i is the judge if and only if cnt1[i] == 0 (trusts nobody) and cnt2[i] == n-1 (trusted by everyone else).

Intuition

The key insight is to think about trust relationships as a directed graph where each person is a node and each trust relationship is a directed edge from the person who trusts to the person being trusted.

In this graph representation, the town judge would have a very specific pattern:

• In-degree: The judge receives n-1 incoming edges (everyone else trusts them)
• Out-degree: The judge has 0 outgoing edges (they trust nobody)

This immediately suggests we need to track two pieces of information for each person:

1. How many people they trust (out-degree)
2. How many people trust them (in-degree)

Instead of building an actual graph, we can simplify this to just counting. For each trust relationship [a, b]:

• Person a trusts someone, so increment their "trusts count"
• Person b is trusted by someone, so increment their "trusted by count"

After processing all trust relationships, we can identify the judge by finding the person who:

• Has a "trusts count" of 0 (trusts nobody)
• Has a "trusted by count" of n-1 (trusted by everyone else)

This counting approach is efficient because we only need to traverse the trust array once to build our counts, then check each person once to find the judge. The uniqueness of the judge (if they exist) is guaranteed by the problem constraints, so we can return immediately when we find someone matching our criteria.

Learn more about Graph patterns.

Solution Approach

The solution uses a counting approach with two arrays to track trust relationships.

Step 1: Initialize Counting Arrays

We create two arrays cnt1 and cnt2, both of size n + 1:

• cnt1[i] tracks how many people person i trusts (out-degree)
• cnt2[i] tracks how many people trust person i (in-degree)

We use size n + 1 to directly map person labels (1 to n) to array indices, leaving index 0 unused.

Step 2: Process Trust Relationships

For each trust relationship [a, b] in the trust array:

• Increment cnt1[a] by 1 (person a trusts someone)
• Increment cnt2[b] by 1 (person b is trusted by someone)

for a, b in trust:
    cnt1[a] += 1  # a trusts someone
    cnt2[b] += 1  # b is trusted by someone

Step 3: Identify the Judge

Iterate through all people from 1 to n and check if person i satisfies both conditions:

• cnt1[i] == 0: Person i trusts nobody
• cnt2[i] == n - 1: Person i is trusted by all other n-1 people

for i in range(1, n + 1):
    if cnt1[i] == 0 and cnt2[i] == n - 1:
        return i

If we find such a person, we immediately return their label as they are the judge. If no person satisfies both conditions after checking everyone, we return -1 to indicate no judge exists.

Time Complexity: O(E + n) where E is the number of trust relationships (edges) Space Complexity: O(n) for the two counting arrays

Example Walkthrough

Let's walk through a concrete example with n = 4 people and trust = [[1,3], [1,4], [2,3], [2,4], [4,3]].

Step 1: Initialize Arrays We create two arrays of size 5 (indices 0-4, where index 0 is unused):

• cnt1 = [0, 0, 0, 0, 0] (tracks who each person trusts)
• cnt2 = [0, 0, 0, 0, 0] (tracks who trusts each person)

Step 2: Process Each Trust Relationship

Processing [1,3]: Person 1 trusts Person 3

• cnt1[1]++ → cnt1 = [0, 1, 0, 0, 0]
• cnt2[3]++ → cnt2 = [0, 0, 0, 1, 0]

Processing [1,4]: Person 1 trusts Person 4

• cnt1[1]++ → cnt1 = [0, 2, 0, 0, 0]
• cnt2[4]++ → cnt2 = [0, 0, 0, 1, 1]

Processing [2,3]: Person 2 trusts Person 3

• cnt1[2]++ → cnt1 = [0, 2, 1, 0, 0]
• cnt2[3]++ → cnt2 = [0, 0, 0, 2, 1]

Processing [2,4]: Person 2 trusts Person 4

• cnt1[2]++ → cnt1 = [0, 2, 2, 0, 0]
• cnt2[4]++ → cnt2 = [0, 0, 0, 2, 2]

Processing [4,3]: Person 4 trusts Person 3

• cnt1[4]++ → cnt1 = [0, 2, 2, 0, 1]
• cnt2[3]++ → cnt2 = [0, 0, 0, 3, 2]

Final arrays:

• cnt1 = [0, 2, 2, 0, 1] (Person 1 trusts 2 people, Person 2 trusts 2 people, Person 3 trusts 0 people, Person 4 trusts 1 person)
• cnt2 = [0, 0, 0, 3, 2] (Person 3 is trusted by 3 people, Person 4 is trusted by 2 people)

Step 3: Find the Judge

Check each person (1 to 4):

• Person 1: cnt1[1] = 2 (trusts 2 people) and cnt2[1] = 0 (trusted by 0 people) → Not the judge
• Person 2: cnt1[2] = 2 (trusts 2 people) and cnt2[2] = 0 (trusted by 0 people) → Not the judge
• Person 3: cnt1[3] = 0 (trusts nobody) and cnt2[3] = 3 (trusted by 3 people) → This matches! (0 == 0 ✓ and 3 == n-1 ✓)
• Person 4: cnt1[4] = 1 (trusts 1 person) and cnt2[4] = 2 (trusted by 2 people) → Not the judge

Result: Person 3 is the town judge because they trust nobody and are trusted by all other 3 people.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m is the length of the trust array and n is the number of people. The algorithm iterates through the trust array once to populate the count arrays (O(m)), then iterates through all n people to find the judge (O(n)), resulting in O(m + n) total time complexity.

The space complexity is O(n), where n is the number of people. The algorithm uses two arrays cnt1 and cnt2, each of size n + 1, to track the trust relationships. Since these are fixed-size arrays that depend only on the number of people and not on the number of trust relationships, the space complexity is O(n).

Note: The reference answer states the complexity in terms of n being the length of the trust array, but this appears to be a notation inconsistency. In the context of this problem, n represents the number of people (as used in the function parameter), and the length of the trust array would be better represented as m or |trust|.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using a Single Array Instead of Two

A common mistake is trying to use a single array to track the "trust balance" (in-degree minus out-degree). While this might seem clever, it fails to distinguish between different scenarios that produce the same balance.

Incorrect Approach:

def findJudge(self, n: int, trust: List[List[int]]) -> int:
    balance = [0] * (n + 1)
    for a, b in trust:
        balance[a] -= 1  # a trusts someone
        balance[b] += 1  # b is trusted
  
    for i in range(1, n + 1):
        if balance[i] == n - 1:  # Wrong check!
            return i
    return -1

Why it fails: A person with balance n-1 might trust one person and be trusted by everyone. For example, if person A trusts B and everyone (including B) trusts A, person A would have a balance of n-1 but isn't the judge because they trust someone.

Correct Solution: Always use two separate arrays to independently track outgoing and incoming trust relationships.

2. Off-by-One Errors with Array Indexing

Since people are numbered from 1 to n, but arrays are 0-indexed, it's easy to make indexing mistakes.

Common Mistakes:

• Creating arrays of size n instead of n + 1
• Starting iteration from 0 instead of 1
• Forgetting that index 0 is unused

Correct Implementation:

# Correct: size n + 1 to accommodate people labeled 1 to n
out_degree = [0] * (n + 1)
in_degree = [0] * (n + 1)

# Correct: iterate from 1 to n (inclusive)
for person in range(1, n + 1):
    # Check conditions

3. Edge Case: Single Person (n = 1)

When there's only one person in town, they are automatically the judge since:

• They trust nobody (trivially true)
• Everyone else trusts them (vacuously true, as there are 0 other people)

Potential Issue: If the trust array is empty and n = 1, ensure your code correctly returns 1, not -1.

Test this edge case:

assert findJudge(1, []) == 1  # Single person is the judge
assert findJudge(2, []) == -1  # Two people, no trust = no judge