Find the Town Judge
EasyPrompt
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: 2Example 2:
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3Example 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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves iterating through each person from 1 to n and checking if they meet the criteria of a town judge. For each person, we scan the entire trust list to verify the two conditions: they trust no one, and everyone else trusts them.
Algorithm
- Loop through each person
ifrom 1 ton, considering them as a potential judge. - For each candidate
i, we need to verify two conditions by scanning the entiretrustarray:- Trusts Nobody: Check if there is any entry
[i, x]in thetrustarray. If one is found,icannot be the judge. - Trusted by Everyone Else: Count the number of people who trust
i. This is the number of entries[x, i]in thetrustarray.
- Trusts Nobody: Check if there is any entry
- If a candidate
itrusts no one AND is trusted by exactlyn - 1people, they are the judge. Returni. - If the loop finishes without finding a judge, it means no one satisfies the conditions. Return -1.
Walkthrough
The algorithm considers every person from 1 to n as a potential candidate for the town judge. For each candidate i, we perform two checks by iterating through the trust array:
- Check if
itrusts anyone: We scan thetrustarray. If we find an entry[i, x], it means candidateitrusts personx, violating the first rule. Thus,icannot be the judge, and we move to the next candidate. - Check if
iis trusted by everyone else: We count how many people trust candidatei. We iterate through thetrustarray and increment a counter for every entry[x, i].
If a candidate i trusts no one (passes check 1) and is trusted by exactly n-1 people (passes check 2), we have found the judge. Since the problem guarantees at most one judge, we can immediately return i. If we check all n people and none satisfy both conditions, it means no judge exists, and we return -1.
class Solution { public int findJudge(int n, int[][] trust) { for (int i = 1; i <= n; i++) { int trustedByCount = 0; boolean trustsSomeone = false; // Check if candidate 'i' trusts anyone for (int[] relation : trust) { if (relation[0] == i) { trustsSomeone = true; break; } } if (trustsSomeone) { continue; // This candidate is disqualified, move to the next } // Check how many people trust candidate 'i' for (int[] relation : trust) { if (relation[1] == i) { trustedByCount++; } } // Check if conditions are met if (trustedByCount == n - 1) { return i; // Found the judge } } return -1; // No judge found }}Complexity
Time
O(N * E), where N is the number of people and E is the number of trust relationships. For each of the N candidates, we iterate through all E relationships.
Space
O(1), as we only use a few variables for counting and flags, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient for larger inputs as it repeatedly scans the
trustarray, leading to a high time complexity.
This approach models the problem as a directed graph where people are nodes and trust relationships are edges. The town judge is a node with an in-degree of n-1 (is trusted by everyone else) and an out-degree of 0 (trusts nobody). We can calculate these degrees for all people in a single pass over the trust array.
Algorithm
- Create two integer arrays,
inDegreeandoutDegree, of sizen + 1, and initialize them to all zeros. - Iterate through each relationship
[a, b]in thetrustarray. - For each relationship, increment
outDegree[a](personatrusts someone) andinDegree[b](personbis trusted by someone). - After populating the arrays, iterate from
i = 1ton. - For each person
i, check ifinDegree[i] == n - 1andoutDegree[i] == 0. - If both conditions are true,
iis the judge. Returni. - If the loop completes without finding a judge, return -1.
Walkthrough
The core idea is to efficiently count the number of people each person trusts (out-degree) and the number of people who trust them (in-degree). Instead of recounting for each candidate, we can pre-calculate these values for everyone.
We use two arrays, inDegree and outDegree, both of size n + 1, initialized to zeros. The extra space is for convenient 1-based indexing.
We iterate through the trust array once. For each relationship [a, b]:
outDegree[a]is incremented, signifying that personatrusts someone.inDegree[b]is incremented, signifying that personbis trusted by someone.
After this single pass, the arrays hold the final degree counts for every person. We then iterate from person 1 to n and check for the one who satisfies the judge's properties: outDegree[i] == 0 and inDegree[i] == n - 1. If we find such a person, we return their label. If the loop completes without finding a judge, we return -1.
class Solution { public int findJudge(int n, int[][] trust) { if (n == 1) { return 1; } int[] inDegree = new int[n + 1]; int[] outDegree = new int[n + 1]; for (int[] relation : trust) { outDegree[relation[0]]++; inDegree[relation[1]]++; } for (int i = 1; i <= n; i++) { if (inDegree[i] == n - 1 && outDegree[i] == 0) { return i; } } return -1; }}Complexity
Time
O(N + E), where N is the number of people and E is the number of trust relationships. We iterate through the `trust` array once (O(E)) and then iterate through the people once (O(N)).
Space
O(N), for the two arrays of size `n+1` used to store the in-degrees and out-degrees.
Trade-offs
Pros
Much more efficient than the brute-force approach with linear time complexity.
The logic directly maps to the graph properties of the judge, making it easy to reason about.
Cons
Uses extra space proportional to the number of people, which could be a concern for very large N.
This is an optimization of the two-array approach. Instead of tracking in-degrees and out-degrees separately, we can use a single array to maintain a "trust score" for each person. A person who trusts someone loses a point, and a person who is trusted gains a point. The judge will be the only person with a final score of n-1.
Algorithm
- Create a single integer array,
trustScores, of sizen + 1, initialized to all zeros. - Iterate through each relationship
[a, b]in thetrustarray. - For each relationship, decrement
trustScores[a]and incrementtrustScores[b]. - After the loop, iterate from
i = 1ton. - If
trustScores[i]is equal ton - 1, then personiis the judge. Returni. - If the loop finishes and no such person is found, return -1.
Walkthrough
This approach refines the degree-counting method by using a single array. The logic is that a town judge must end up with a score of n - 1. This is because:
- The judge is trusted by
n - 1other people, so their score gets incrementedn - 1times. - The judge trusts no one, so their score is never decremented.
- Any other person
ieither trusts someone (their score is decremented at least once, so it can't ben-1) or is not trusted by everyone (their score won't reachn-1).
The algorithm proceeds as follows:
- Create a single array,
trustScores, of sizen + 1, initialized to zeros. - Iterate through the
trustarray. For each relationship[a, b]:- Decrement the score of the truster:
trustScores[a]--. - Increment the score of the trustee:
trustScores[b]++.
- Decrement the score of the truster:
- After the loop, iterate from person 1 to
n. - If any person
ihastrustScores[i] == n - 1, they are the judge. Returni. - If no such person is found, return -1.
This approach is elegant as it combines the two conditions into a single score check.
class Solution { public int findJudge(int n, int[][] trust) { if (n == 1) { return 1; } int[] trustScores = new int[n + 1]; for (int[] relation : trust) { // Person 'a' trusts someone, their score decreases. trustScores[relation[0]]--; // Person 'b' is trusted by someone, their score increases. trustScores[relation[1]]++; } for (int i = 1; i <= n; i++) { // The judge is trusted by n-1 people and trusts no one. if (trustScores[i] == n - 1) { return i; } } return -1; }}Complexity
Time
O(N + E), where N is the number of people and E is the number of trust relationships. We make one pass over the trust relationships (O(E)) and one pass over the people (O(N)).
Space
O(N), for the single array of size `n+1` used to store the trust scores.
Trade-offs
Pros
Most efficient in terms of time and space (among these three).
The logic is concise and combines two conditions into one check.
Uses half the space of the two-array approach.
Cons
The logic of using a single score might be slightly less intuitive at first glance compared to separate in/out degree counts.
Solutions
Solution
class Solution {public int findJudge(int n, int[][] trust) { int[] cnt1 = new int[n + 1]; int[] cnt2 = new int[n + 1]; for (var t : trust) { int a = t[0], b = t[1]; ++cnt1[a]; ++cnt2[b]; } for (int i = 1; i <= n; ++i) { if (cnt1[i] == 0 && cnt2[i] == n - 1) { return i; } } return -1; }}class Solution {public: int findJudge(int n, vector<vector<int>> &trust) { vector<int> cnt1(n + 1); vector<int> cnt2(n + 1); for (auto &t : trust) { int a = t[0], b = t[1]; ++cnt1[a]; ++cnt2[b]; } for (int i = 1; i <= n; ++i) { if (cnt1[i] == 0 && cnt2[i] == n - 1) { return i; } } return -1; }};class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: cnt1 = [0] * (n + 1) cnt2 = [0] * (n + 1) for a, b in trust: cnt1[a] += 1 cnt2[b] += 1 for i in range(1, n + 1): if cnt1[i] == 0 and cnt2[i] == n - 1: return i return - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.