Find the Town Judge - Solution & Explanation
Problem Statement
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.
- There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
Example 1:
Input: n = 2, trust = [[1,2]] Output: 2
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
Constraints:
1 <= n <= 10000 <= trust.length <= 104trust[i].length == 2- All the pairs of
trustare unique. ai != bi1 <= ai, bi <= n
Approach Overview
Problem Overview: You have n people in a town labeled from 1 to n. Some people trust others, represented as pairs [a, b]. The town judge trusts nobody but is trusted by everyone else. Your task is to identify that person or return -1 if such a person does not exist.
Approach 1: In-Degree and Out-Degree Calculation (O(n + m) time, O(n) space)
This problem maps naturally to a graph interpretation where each person is a node and each trust pair is a directed edge from a to b. The judge must have out-degree = 0 (trusts nobody) and in-degree = n - 1 (trusted by everyone else). Iterate through the trust list and update two arrays: one tracking how many people each person trusts, and another tracking how many trust them. After processing all edges, scan people from 1 to n and return the person whose in-degree is n - 1 and out-degree is 0. The algorithm processes each trust pair once, giving O(n + m) time and O(n) space.
Approach 2: Graph Representation Using Single Array (O(n + m) time, O(n) space)
You can compress the in-degree and out-degree idea into one array. Maintain a score array where trusting someone decreases your score and being trusted increases it. For each pair [a, b], decrement score[a] and increment score[b]. After processing all pairs, the judge must end up with score n - 1 because they receive n - 1 trusts and give none. This approach keeps the same linear time complexity while reducing bookkeeping to a single array. The trust relationships are still treated as edges in a conceptual graph structure, but the representation is simplified.
Recommended for interviews: The single-array scoring approach is usually preferred. It shows you recognized the key property of the judge and optimized the graph representation. Explaining the in-degree/out-degree version first demonstrates solid graph reasoning, while the compressed array solution shows practical optimization and clean implementation.
Approach 1: In-Degree and Out-Degree Calculation
The idea is to calculate the in-degree and out-degree for each person. A person is the town judge if their in-degree is n-1 (trusted by all other n-1 people) and their out-degree is 0 (trusting no one).
This C program uses two arrays to store in-degrees and out-degrees of each person. It then iterates through the trust array to update these values accordingly. Finally, it searches for a person whose in-degree is n-1 and out-degree is 0, identifying them as the judge if they exist.
Complexity
Time Complexity: O(trust.length), where trust.length is the total number of trust relationships.
Space Complexity: O(n), where n is the number of people in the town.
Approach 2: Graph Representation Using Single Array
An alternative approach is to use a single array to calculate the difference between in-degrees and out-degrees. For the judge, this difference should be n-1.
This C implementation uses a single array to track the net trust value of each person. A candidate judge should have a net positive trust equal to n-1.
Complexity
Time Complexity: O(trust.length)
Space Complexity: O(n)
Approach 3: Counting
We create two arrays cnt1 and cnt2 of length n + 1, representing the number of people each person trusts and the number of people who trust each person, respectively.
Next, we traverse the array trust, for each item [a_i, b_i], we increment cnt1[a_i] and cnt2[b_i] by 1.
Finally, we enumerate each person i in the range [1,..n]. If cnt1[i] = 0 and cnt2[i] = n - 1, it means that i is the town judge, and we return i. Otherwise, if no such person is found after the traversal, we return -1.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array trust.
Complexity Comparison
| Approach | Complexity |
|---|---|
| In-Degree and Out-Degree Calculation | Time Complexity: O(trust.length), where trust.length is the total number of trust relationships. |
| Graph Representation Using Single Array | Time Complexity: O(trust.length) |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Degree and Out-Degree Calculation | O(n + m) | O(n) | When explaining graph fundamentals or making trust relationships explicit |
| Graph Representation Using Single Array | O(n + m) | O(n) | Preferred interview solution with simpler implementation and less bookkeeping |
Video Solution
Find the Town Judge - Leetcode 997 - Python • NeetCodeIO • 28,282 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Town Judge easy or hard?
Find the Town Judge Python/Java solution
How to solve Find the Town Judge in O(n)?
What is the best approach for Find the Town Judge?
Is Find the Town Judge asked at Google/Amazon/Meta?
What data structure is used in Find the Town Judge?
What is the time complexity of Find the Town Judge?
Ready to solve this problem?
Practice Find the Town Judge with our built-in code editor and test cases.
Practice on FleetCode