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 <= nThe key observation in #997 Find the Town Judge is that the judge has two defining properties: they trust nobody and are trusted by everyone else. If there are n people in the town, the judge must have exactly n-1 people trusting them.
A practical way to model this is using a graph perspective. Each trust pair [a, b] represents a directed edge from a to b. The judge will have in-degree = n-1 and out-degree = 0. Instead of storing full adjacency structures, you can maintain a single score array where trusting someone decreases a person's score and being trusted increases it. The judge will end with a score of n-1.
This approach efficiently processes each trust relationship once, giving linear time complexity. It also uses only a small auxiliary array, making the space usage minimal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-degree / Trust Score Array | O(n + m) | O(n) |
Nick White
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).
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int findJudge(int n, int** trust, int trustSize, int* trustColSize) {
5 int* inDegrees = (int*)calloc(n + 1, sizeof(int));
6 int* outDegrees = (int*)calloc(n + 1, sizeof(int));
7
8 for (int i = 0; i < trustSize; i++) {
9 int a = trust[i][0];
10 int b = trust[i][1];
11 outDegrees[a]++;
12 inDegrees[b]++;
13 }
14
15 for (int i = 1; i <= n; i++) {
16 if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
17 free(inDegrees);
18 free(outDegrees);
19 return i;
20 }
21 }
22
23 free(inDegrees);
24 free(outDegrees);
25 return -1;
26}
27This 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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it can be viewed as a directed graph problem where trust relationships represent edges. The town judge corresponds to a node with in-degree n-1 and out-degree 0.
Yes, this problem is commonly used in coding interviews to test understanding of graph basics, counting techniques, and edge-case reasoning. It is especially popular for beginner-level interview practice.
An integer array is typically sufficient to track trust scores for each person. This avoids building a full graph structure and keeps the solution simple and efficient.
The optimal approach uses a trust score or in-degree/out-degree concept. For every trust pair, decrease the score of the person who trusts and increase the score of the person being trusted. The town judge will have a final score of 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.