How do you solve Find the Town Judge on LeetCode?

Find the Town Judge (LeetCode #997) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The town judge must be trusted by everyone else, which means their trust count must be n-1.

What is the brute force solution for Find the Town Judge?

The brute force approach for Find the Town Judge is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we check each person to see if they could be the judge by validating the trust relationships. This method is straightforward but inefficient as it involves checking all pairs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Find the Town Judge?

Find the Town Judge uses the following concepts: Array, Hash Table, Graph Theory. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Find the Town Judge?

Clarify the problem statement and constraints before jumping to coding. Think about edge cases, such as when trust is empty or when n is small. Explain your thought process clearly while coding to show your understanding.

What are common mistakes when solving Find the Town Judge?

Assuming there can be multiple judges or no judges without properly checking conditions. Not considering edge cases where trust relationships are empty.

#997

Find the Town Judge

Easy

ArrayHash TableGraph TheoryHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a counting approach to track how many people trust each person and how many people each person trusts. This allows us to identify the judge efficiently.

⚙️

Algorithm

3 steps

1Step 1: Create two arrays: one to count how many people trust each person and another to count how many people each person trusts.
2Step 2: Iterate through the trust relationships and update the counts accordingly.
3Step 3: Check for the person who is trusted by n-1 people and trusts nobody.

solution.py10 lines

1def findJudge(n, trust):
2    trust_count = [0] * (n + 1)
3    trusted_by_count = [0] * (n + 1)
4    for a, b in trust:
5        trust_count[a] += 1
6        trusted_by_count[b] += 1
7    for i in range(1, n + 1):
8        if trust_count[i] == 0 and trusted_by_count[i] == n - 1:
9            return i
10    return -1

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the trust array once and then through the people once. The space complexity is O(n) due to the two arrays used to count trust relationships.

1The town judge must be trusted by everyone else, which means their trust count must be n-1.
2The town judge trusts nobody, which means their own trust count must be 0.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.