Find the Town Judge solution and explanation
Google
9 more videos on this problem
Find the Town Judge - Leetcode 997 - PythonNeetCodeIO · 9:55 · 28K views
LeetCode 997. Find The Town Judge (Algorithm Explained)Nick White · 6:06 · 22K views
Find the town judge | Leetcode #997Techdose · 8:39 · 20K views
Find the Town Judge | 2 Approaches | Leetcode 997codestorywithMIK · 10:43 · 10K views
Find the Town Judge | LeetCode 997 | Coding Interview TutorialTerrible Whiteboard · 12:52 · 5K views
Find the Town Judge - 997 Leetcode PythonPersistent Programmer · 15:07 · 1K views
(Old) Leetcode 997 - Find the Town Judge | GraphNideesh Terapalli · 7:23 · 1K views
Find the Town Judge | Leetcode 997 | Live coding session 🔥🔥🔥 | O(n) Linear | Graph theory basicsCoding Decoded · 7:00 · 1K views
Leetcode | 997. Find the Town Judge | Easy | Java SolutionDeveloper Docs · 9:40 · 887 views
Find the Town Judge LeetCode Solution Java | LeetCode 997 | Programming TutorialsProgramming Tutorials · 15:06 · 834 views
The problem
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).
def findJudge(n, trust):
in_degrees = [0] * (n + 1)
out_degrees = [0] * (n + 1)
for a, b in trust:
out_degrees[a] += 1
in_degrees[b] += 1
for i in range(1, n + 1):
if in_degrees[i] == n - 1 and out_degrees[i] == 0:
return i
return -1class Solution {
public int findJudge(int n, int[][] trust) {
int[] inDegrees = new int[n + 1];
int[] outDegrees = new int[n + 1];
for (int[] t : trust) {
int a = t[0], b = t[1];
outDegrees[a]++;
inDegrees[b]++;
}
for (int i = 1; i <= n; i++) {
if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
return i;
}
}
return -1;
}
}#include <vector>
using namespace std;
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> inDegrees(n + 1, 0);
vector<int> outDegrees(n + 1, 0);
for (auto& relation : trust) {
int a = relation[0];
int b = relation[1];
outDegrees[a]++;
inDegrees[b]++;
}
for (int i = 1; i <= n; i++) {
if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
return i;
}
}
return -1;
}var findJudge = function(n, trust) {
const inDegrees = new Array(n + 1).fill(0);
const outDegrees = new Array(n + 1).fill(0);
for (const [a, b] of trust) {
outDegrees[a]++;
inDegrees[b]++;
}
for (let i = 1; i <= n; i++) {
if (inDegrees[i] === n - 1 && outDegrees[i] === 0) {
return i;
}
}
return -1;
};#include <stdio.h>
#include <stdlib.h>
int findJudge(int n, int** trust, int trustSize, int* trustColSize) {
int* inDegrees = (int*)calloc(n + 1, sizeof(int));
int* outDegrees = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < trustSize; i++) {
int a = trust[i][0];
int b = trust[i][1];
outDegrees[a]++;
inDegrees[b]++;
}
for (int i = 1; i <= n; i++) {
if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
free(inDegrees);
free(outDegrees);
return i;
}
}
free(inDegrees);
free(outDegrees);
return -1;
}public class Solution {
public int FindJudge(int n, int[][] trust) {
int[] inDegrees = new int[n + 1];
int[] outDegrees = new int[n + 1];
foreach (var t in trust) {
int a = t[0], b = t[1];
outDegrees[a]++;
inDegrees[b]++;
}
for (int i = 1; i <= n; i++) {
if (inDegrees[i] == n - 1 && outDegrees[i] == 0) {
return i;
}
}
return -1;
}
}This Python function counts the number of people each individual trusts and the number of people who trust them using two separate lists. It then searches for a person who is trusted by n-1 others while trusting no one.
Time Complexity: O(trust.length), where trust.length is the number of trust pairs.
Space Complexity: O(n), with n being the number of residents 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.
def findJudge(n, trust):
net_trust = [0] * (n + 1)
for a, b in trust:
net_trust[a] -= 1
net_trust[b] += 1
for i in range(1, n + 1):
if net_trust[i] == n - 1:
return i
return -1class Solution {
public int findJudge(int n, int[][] trust) {
int[] netTrust = new int[n + 1];
for (int[] t : trust) {
int a = t[0], b = t[1];
netTrust[a]--;
netTrust[b]++;
}
for (int i = 1; i <= n; i++) {
if (netTrust[i] == n - 1) {
return i;
}
}
return -1;
}
}#include <vector>
using namespace std;
int findJudge(int n, vector<vector<int>>& trust) {
vector<int> netTrust(n + 1, 0);
for (auto& t : trust) {
int a = t[0], b = t[1];
netTrust[a]--;
netTrust[b]++;
}
for (int i = 1; i <= n; i++) {
if (netTrust[i] == n - 1) {
return i;
}
}
return -1;
}var findJudge = function(n, trust) {
const netTrust = new Array(n + 1).fill(0);
for (const [a, b] of trust) {
netTrust[a]--;
netTrust[b]++;
}
for (let i = 1; i <= n; i++) {
if (netTrust[i] === n - 1) {
return i;
}
}
return -1;
};#include <stdio.h>
#include <stdlib.h>
int findJudge(int n, int** trust, int trustSize, int* trustColSize) {
int* netTrust = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < trustSize; i++) {
int a = trust[i][0];
int b = trust[i][1];
netTrust[a]--;
netTrust[b]++;
}
for (int i = 1; i <= n; i++) {
if (netTrust[i] == n - 1) {
free(netTrust);
return i;
}
}
free(netTrust);
return -1;
}public class Solution {
public int FindJudge(int n, int[][] trust) {
int[] netTrust = new int[n + 1];
foreach (var t in trust) {
int a = t[0], b = t[1];
netTrust[a]--;
netTrust[b]++;
}
for (int i = 1; i <= n; i++) {
if (netTrust[i] == n - 1) {
return i;
}
}
return -1;
}
}Python solution with a single net trust list updating trust values. Only a judge will have a net trust of n-1, indicating they are trusted by all other citizens.
Time Complexity: O(len(trust))
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.
function findJudge(n: number, trust: number[][]): number {
const cnt1: number[] = new Array(n + 1).fill(0);
const cnt2: number[] = new Array(n + 1).fill(0);
for (const [a, b] of trust) {
++cnt1[a];
++cnt2[b];
}
for (let i = 1; i <= n; ++i) {
if (cnt1[i] === 0 && cnt2[i] === n - 1) {
return i;
}
}
return -1;
}func findJudge(n int, trust [][]int) int {
cnt1 := make([]int, n+1)
cnt2 := make([]int, n+1)
for _, t := range trust {
a, b := t[0], t[1]
cnt1[a]++
cnt2[b]++
}
for i := 1; i <= n; i++ {
if cnt1[i] == 0 && cnt2[i] == n-1 {
return i
}
}
return -1
}impl Solution {
pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 {
let mut cnt1 = vec![0; (n + 1) as usize];
let mut cnt2 = vec![0; (n + 1) as usize];
for t in trust.iter() {
let a = t[0] as usize;
let b = t[1] as usize;
cnt1[a] += 1;
cnt2[b] += 1;
}
for i in 1..=n as usize {
if cnt1[i] == 0 && cnt2[i] == (n as usize) - 1 {
return i as i32;
}
}
-1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| In-Degree and Out-Degree Calculation | Time Complexity: O(trust.length), where trust.length is the number of trust pairs. |
| Graph Representation Using Single Array | Time Complexity: O(len(trust)) |
| Counting | – |
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 |
Frequently asked questions
Is Find the Town Judge easy or hard?
Find the Town Judge is classified as an Easy problem on LeetCode with about a 50% acceptance rate. The challenge is recognizing the graph property that the judge has zero outgoing edges and n - 1 incoming edges.
Find the Town Judge Python/Java solution
The typical Python or Java implementation uses a single integer array of size n + 1 to store trust scores. Iterate through the trust list, decrement the truster's score and increment the trustee's score, then scan for the person whose score equals n - 1.
How to solve Find the Town Judge in O(n)?
Use degree counting from graph theory. Track how many people trust each person (in-degree) and how many people each person trusts (out-degree). The judge must have in-degree n - 1 and out-degree 0. Processing the trust list once and scanning the result gives O(n + m) time complexity.
What is the best approach for Find the Town Judge?
The most efficient approach uses a single score array that tracks trust relationships. Decrease the score for the person who trusts someone and increase it for the person being trusted. After processing all pairs, the judge must have a score of n - 1. This runs in O(n + m) time and O(n) space.
Is Find the Town Judge asked at Google/Amazon/Meta?
Find the Town Judge is a common entry-level graph reasoning problem frequently used in coding interviews and online assessments. Variations of degree counting and graph relationship problems appear at companies like Amazon, Google, and other large tech firms.
What data structure is used in Find the Town Judge?
The problem primarily uses arrays to track in-degree and out-degree counts for each person. Conceptually it represents a directed graph of trust relationships, but an explicit adjacency list or matrix is unnecessary for the optimal solution.
What is the time complexity of Find the Town Judge?
The optimal solution runs in O(n + m) time where n is the number of people and m is the number of trust pairs. Each trust relationship is processed once and then the algorithm performs a single pass over the people to find the judge. Space complexity is O(n).