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:
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 == 2trust are unique.ai != bi1 <= ai, bi <= nProblem 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.
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.
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.
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.
Time Complexity: O(trust.length)
Space Complexity: O(n)
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.
| 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 | — |
| 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 |
Find the Town Judge - Leetcode 997 - Python • NeetCodeIO • 26,859 views views
Watch 9 more video solutions →Practice Find the Town Judge with our built-in code editor and test cases.
Practice on FleetCode