Find the Town Judge

🎯

Find the Town Judge

easyGRAPHAmazonGoogle

In a small town, everyone trusts exactly one person except the town judge, who trusts nobody but is trusted by everyone else. Can you find out who the judge is?

💡 This problem is about understanding relationships in a directed graph using trust as edges. Beginners often struggle because they try to check all conditions naively without leveraging in-degree and out-degree concepts, which simplifies the problem drastically.

📋

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: 1. The town judge trusts nobody. 2. Everybody (except for the town judge) trusts the town judge. Given an array trust where trust[i] = [a, b] representing that the person labeled a trusts the person labeled b, return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

1 ≤ n ≤ 10^50 ≤ trust.length ≤ 10^6trust[i].length == 21 ≤ trust[i][0], trust[i][1] ≤ ntrust[i][0] != trust[i][1]

💡

Example

Input"n = 3, trust = [[1,3],[2,3]]"

Output3

Person 3 is trusted by persons 1 and 2 and trusts nobody, so 3 is the town judge.

Input"n = 3, trust = [[1,3],[2,3],[3,1]]"

Output-1

Person 3 trusts person 1, so cannot be the judge.

• n = 1, trust = [] → 1 (single person is trivially the judge)
• trust = [] with n > 1 → -1 (no trust relationships means no judge)
• trust contains cycles → -1 (judge cannot trust anyone)
• multiple people trusted by everyone but also trust others → -1 (no unique judge)

⚠️

Common Mistakes

Not checking that the judge trusts nobody

Incorrectly identifying a person who is trusted but also trusts others as judge

✅ Ensure out-degree or trust count for candidate is zero

Assuming trust relationships are symmetric

Wrongly concluding mutual trust implies judge status

✅ Remember trust is directed; check in-degree and out-degree separately

Not handling the case n=1 correctly

Returning -1 when single person should be judge

✅ Return 1 if n=1 and trust list is empty

Using nested loops on large inputs

Time limit exceeded or slow performance

✅ Use counting arrays to achieve linear time

Not verifying uniqueness of judge

Returning a candidate when multiple satisfy conditions

✅ Check that only one person meets the judge criteria

🧠

Brute Force (Check Each Person by Scanning Trust List)

💡 This approach exists to build intuition by directly verifying the judge conditions for each person without optimization. It helps beginners understand the problem constraints and the meaning of trust relationships.

Intuition

For each person, check if they trust nobody and if everyone else trusts them by scanning the entire trust list.

Algorithm

1. For each person from 1 to n:
2. Check if this person trusts nobody by scanning the trust list.
3. Check if everyone else trusts this person by scanning the trust list.
4. If both conditions hold, return this person as the judge.
5. If no person satisfies both conditions, return -1.

💡 The nested scanning makes it hard to see efficiency, but it clearly matches the problem definition.

</>

Code

def findJudge(n, trust):
    for candidate in range(1, n+1):
        trusts_someone = False
        trusted_by_count = 0
        for a, b in trust:
            if a == candidate:
                trusts_someone = True
                break
        if trusts_someone:
            continue
        for a, b in trust:
            if b == candidate:
                trusted_by_count += 1
        if trusted_by_count == n - 1:
            return candidate
    return -1

# Driver code
if __name__ == '__main__':
    print(findJudge(3, [[1,3],[2,3]]))  # Output: 3
    print(findJudge(3, [[1,3],[2,3],[3,1]]))  # Output: -1

Line Notes

for candidate in range(1, n+1):Iterate over each person as a potential judge

if a == candidate:Check if candidate trusts someone, disqualify if yes

if trusts_someone:Skip candidate if they trust anyone

if trusted_by_count == n - 1:Judge must be trusted by everyone else

import java.util.*;
public class Solution {
    public static int findJudge(int n, int[][] trust) {
        for (int candidate = 1; candidate <= n; candidate++) {
            boolean trustsSomeone = false;
            int trustedByCount = 0;
            for (int[] t : trust) {
                if (t[0] == candidate) {
                    trustsSomeone = true;
                    break;
                }
            }
            if (trustsSomeone) continue;
            for (int[] t : trust) {
                if (t[1] == candidate) trustedByCount++;
            }
            if (trustedByCount == n - 1) return candidate;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(findJudge(3, new int[][]{{1,3},{2,3}})); // 3
        System.out.println(findJudge(3, new int[][]{{1,3},{2,3},{3,1}})); // -1
    }
}

Line Notes

for (int candidate = 1; candidate <= n; candidate++) {Try each person as judge candidate

if (t[0] == candidate) {Check if candidate trusts anyone

if (trustsSomeone) continue;Skip candidate if they trust someone

if (trustedByCount == n - 1) return candidate;Judge must be trusted by all others

#include <iostream>
#include <vector>
using namespace std;

int findJudge(int n, vector<vector<int>>& trust) {
    for (int candidate = 1; candidate <= n; candidate++) {
        bool trustsSomeone = false;
        int trustedByCount = 0;
        for (auto& t : trust) {
            if (t[0] == candidate) {
                trustsSomeone = true;
                break;
            }
        }
        if (trustsSomeone) continue;
        for (auto& t : trust) {
            if (t[1] == candidate) trustedByCount++;
        }
        if (trustedByCount == n - 1) return candidate;
    }
    return -1;
}

int main() {
    vector<vector<int>> trust1{{1,3},{2,3}};
    cout << findJudge(3, trust1) << endl; // 3
    vector<vector<int>> trust2{{1,3},{2,3},{3,1}};
    cout << findJudge(3, trust2) << endl; // -1
    return 0;
}

Line Notes

for (int candidate = 1; candidate <= n; candidate++) {Check each person as judge candidate

if (t[0] == candidate) {Check if candidate trusts anyone

if (trustsSomeone) continue;Skip candidate if they trust someone

if (trustedByCount == n - 1) return candidate;Judge must be trusted by all others

function findJudge(n, trust) {
    for (let candidate = 1; candidate <= n; candidate++) {
        let trustsSomeone = false;
        let trustedByCount = 0;
        for (const [a, b] of trust) {
            if (a === candidate) {
                trustsSomeone = true;
                break;
            }
        }
        if (trustsSomeone) continue;
        for (const [a, b] of trust) {
            if (b === candidate) trustedByCount++;
        }
        if (trustedByCount === n - 1) return candidate;
    }
    return -1;
}

// Test cases
console.log(findJudge(3, [[1,3],[2,3]])); // 3
console.log(findJudge(3, [[1,3],[2,3],[3,1]])); // -1

Line Notes

for (let candidate = 1; candidate <= n; candidate++) {Try each person as judge candidate

if (a === candidate) {Check if candidate trusts anyone

if (trustsSomeone) continue;Skip candidate if they trust someone

if (trustedByCount === n - 1) return candidate;Judge must be trusted by all others

⏱

Complexity

TimeO(n * m) where m = trust.length

SpaceO(1) additional space

For each of the n people, we scan the trust list of length m twice, resulting in O(n*m) time.

💡 If n=1000 and m=1000, this means up to 1,000,000 operations, which is inefficient for large inputs.

Interview Verdict: TLE for large inputs, but useful for initial understanding

This approach is too slow for big inputs but helps grasp the problem and verify correctness on small cases.

🧠

Better Approach Using In-degree and Out-degree Arrays

💡 This approach improves efficiency by counting how many people trust each person (in-degree) and how many people each person trusts (out-degree), avoiding repeated scans.

Intuition

The town judge has in-degree = n-1 (trusted by everyone else) and out-degree = 0 (trusts nobody). We can track these counts in arrays.

Algorithm

1. Initialize two arrays in_degree and out_degree of size n+1 with zeros.
2. For each trust pair [a, b], increment out_degree[a] and in_degree[b].
3. Iterate over each person from 1 to n:
4. If in_degree[i] == n-1 and out_degree[i] == 0, return i as the judge.
5. If no such person found, return -1.

💡 This approach avoids nested loops by summarizing trust counts, making it easier to check conditions.

</>

Code

def findJudge(n, trust):
    in_degree = [0] * (n + 1)
    out_degree = [0] * (n + 1)
    for a, b in trust:
        out_degree[a] += 1
        in_degree[b] += 1
    for i in range(1, n + 1):
        if in_degree[i] == n - 1 and out_degree[i] == 0:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(findJudge(3, [[1,3],[2,3]]))  # Output: 3
    print(findJudge(3, [[1,3],[2,3],[3,1]]))  # Output: -1

Line Notes

in_degree = [0] * (n + 1)Initialize in-degree counts for all people

out_degree = [0] * (n + 1)Initialize out-degree counts for all people

for a, b in trust:Count trust relationships

if in_degree[i] == n - 1 and out_degree[i] == 0:Judge conditions: trusted by all others, trusts no one

import java.util.*;
public class Solution {
    public static int findJudge(int n, int[][] trust) {
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int[] t : trust) {
            outDegree[t[0]]++;
            inDegree[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(findJudge(3, new int[][]{{1,3},{2,3}})); // 3
        System.out.println(findJudge(3, new int[][]{{1,3},{2,3},{3,1}})); // -1
    }
}

Line Notes

int[] inDegree = new int[n + 1];Create array to count incoming trusts

int[] outDegree = new int[n + 1];Create array to count outgoing trusts

for (int[] t : trust) {Update counts for each trust pair

if (inDegree[i] == n - 1 && outDegree[i] == 0) return i;Check if person is judge

#include <iostream>
#include <vector>
using namespace std;

int findJudge(int n, vector<vector<int>>& trust) {
    vector<int> inDegree(n + 1, 0);
    vector<int> outDegree(n + 1, 0);
    for (auto& t : trust) {
        outDegree[t[0]]++;
        inDegree[t[1]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == n - 1 && outDegree[i] == 0) return i;
    }
    return -1;
}

int main() {
    vector<vector<int>> trust1{{1,3},{2,3}};
    cout << findJudge(3, trust1) << endl; // 3
    vector<vector<int>> trust2{{1,3},{2,3},{3,1}};
    cout << findJudge(3, trust2) << endl; // -1
    return 0;
}

Line Notes

vector<int> inDegree(n + 1, 0);Initialize in-degree vector

vector<int> outDegree(n + 1, 0);Initialize out-degree vector

for (auto& t : trust) {Count trust relationships

if (inDegree[i] == n - 1 && outDegree[i] == 0) return i;Judge must be trusted by all others and trust none

function findJudge(n, trust) {
    const inDegree = new Array(n + 1).fill(0);
    const outDegree = new Array(n + 1).fill(0);
    for (const [a, b] of trust) {
        outDegree[a]++;
        inDegree[b]++;
    }
    for (let i = 1; i <= n; i++) {
        if (inDegree[i] === n - 1 && outDegree[i] === 0) return i;
    }
    return -1;
}

// Test cases
console.log(findJudge(3, [[1,3],[2,3]])); // 3
console.log(findJudge(3, [[1,3],[2,3],[3,1]])); // -1

Line Notes

const inDegree = new Array(n + 1).fill(0);Initialize in-degree array

const outDegree = new Array(n + 1).fill(0);Initialize out-degree array

for (const [a, b] of trust) {Count trust relationships

if (inDegree[i] === n - 1 && outDegree[i] === 0) return i;Judge conditions check

⏱

Complexity

TimeO(n + m) where m = trust.length

SpaceO(n) for in-degree and out-degree arrays

We iterate once over the trust list and once over the people, resulting in linear time.

💡 For n=100000 and m=1000000, this approach is efficient and scalable.

Interview Verdict: Accepted and efficient for large inputs

This approach is optimal for this problem and should be coded in interviews.

🧠

Optimal Approach Using a Single Trust Score Array

💡 This approach further optimizes space by using a single array to track net trust score, combining in-degree and out-degree into one metric.

Intuition

Increase score by 1 for each time a person is trusted, decrease by 1 for each time they trust someone. The judge will have a score of n-1.

Algorithm

1. Initialize an array trust_score of size n+1 with zeros.
2. For each trust pair [a, b], decrement trust_score[a] by 1 and increment trust_score[b] by 1.
3. Iterate over each person from 1 to n:
4. If trust_score[i] == n-1, return i as the judge.
5. If no such person found, return -1.

💡 This approach cleverly combines in-degree and out-degree into one metric, simplifying checks.

</>

Code

def findJudge(n, trust):
    trust_score = [0] * (n + 1)
    for a, b in trust:
        trust_score[a] -= 1
        trust_score[b] += 1
    for i in range(1, n + 1):
        if trust_score[i] == n - 1:
            return i
    return -1

# Driver code
if __name__ == '__main__':
    print(findJudge(3, [[1,3],[2,3]]))  # Output: 3
    print(findJudge(3, [[1,3],[2,3],[3,1]]))  # Output: -1

Line Notes

trust_score = [0] * (n + 1)Initialize net trust score array

trust_score[a] -= 1Person a trusts someone, decrease score

trust_score[b] += 1Person b is trusted, increase score

if trust_score[i] == n - 1:Judge has score n-1, trusted by all others and trusts none

import java.util.*;
public class Solution {
    public static int findJudge(int n, int[][] trust) {
        int[] trustScore = new int[n + 1];
        for (int[] t : trust) {
            trustScore[t[0]]--;
            trustScore[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (trustScore[i] == n - 1) return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(findJudge(3, new int[][]{{1,3},{2,3}})); // 3
        System.out.println(findJudge(3, new int[][]{{1,3},{2,3},{3,1}})); // -1
    }
}

Line Notes

int[] trustScore = new int[n + 1];Initialize net trust score array

trustScore[t[0]]--;Decrease score for trusting someone

trustScore[t[1]]++;Increase score for being trusted

if (trustScore[i] == n - 1) return i;Judge has net score n-1

#include <iostream>
#include <vector>
using namespace std;

int findJudge(int n, vector<vector<int>>& trust) {
    vector<int> trustScore(n + 1, 0);
    for (auto& t : trust) {
        trustScore[t[0]]--;
        trustScore[t[1]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (trustScore[i] == n - 1) return i;
    }
    return -1;
}

int main() {
    vector<vector<int>> trust1{{1,3},{2,3}};
    cout << findJudge(3, trust1) << endl; // 3
    vector<vector<int>> trust2{{1,3},{2,3},{3,1}};
    cout << findJudge(3, trust2) << endl; // -1
    return 0;
}

Line Notes

vector<int> trustScore(n + 1, 0);Initialize net trust score vector

trustScore[t[0]]--;Decrease score for trusting someone

trustScore[t[1]]++;Increase score for being trusted

if (trustScore[i] == n - 1) return i;Judge has net score n-1

function findJudge(n, trust) {
    const trustScore = new Array(n + 1).fill(0);
    for (const [a, b] of trust) {
        trustScore[a]--;
        trustScore[b]++;
    }
    for (let i = 1; i <= n; i++) {
        if (trustScore[i] === n - 1) return i;
    }
    return -1;
}

// Test cases
console.log(findJudge(3, [[1,3],[2,3]])); // 3
console.log(findJudge(3, [[1,3],[2,3],[3,1]])); // -1

Line Notes

const trustScore = new Array(n + 1).fill(0);Initialize net trust score array

trustScore[a]--;Decrease score for trusting someone

trustScore[b]++;Increase score for being trusted

if (trustScore[i] === n - 1) return i;Judge has net score n-1

⏱

Complexity

TimeO(n + m) where m = trust.length

SpaceO(n) for trust_score array

Single pass over trust list and people, linear time and space.

💡 This is the most concise and efficient approach for large inputs.

Interview Verdict: Accepted and optimal

This is the best approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal single array approach is best for interviews; brute force is only for initial explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * m)	O(1)	No	N/A	Mention only - never code
2. In-degree and Out-degree Arrays	O(n + m)	O(n)	No	N/A	Good to explain and code if time permits
3. Single Trust Score Array	O(n + m)	O(n)	No	N/A	Best approach to code in interview

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the in-degree/out-degree optimization.Step 4: Present the optimal single array trust score approach.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to model the problem as graph in-degree/out-degree, optimize from brute force to linear time, and write clean code.

Common Follow-ups

• What if there are multiple judges? → Return -1 since judge must be unique.
• How to handle very large inputs efficiently? → Use the optimal O(n + m) approach with arrays.

💡 Follow-ups test your understanding of uniqueness and scalability.

🔍

Pattern Recognition

When to Use

1) Problem involves directed trust or relationship edges; 2) Need to find a unique node with special in/out degree; 3) Conditions about trusting nobody but trusted by all; 4) Input given as pairs representing directed edges.

Signature Phrases

'The town judge trusts nobody''Everybody trusts the town judge'

NOT This Pattern When

Problems involving undirected graphs or cycles without trust direction are different patterns.

Similar Problems

Find the Celebrity - similar in-degree/out-degree logicCourse Schedule - uses graph edges and in-degree conceptsAlien Dictionary - ordering based on directed edges

Practice

1. Given the following code snippet for finding the cheapest flight within K stops, what is the returned output for the input: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, K=1?

from collections import defaultdict
import heapq

def findCheapestPrice(n, flights, src, dst, K):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    heap = [(0, src, 0)]  # cost, node, stops
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops <= K:
            for nei, price in graph[node]:
                heapq.heappush(heap, (cost + price, nei, stops + 1))
    return -1

print(findCheapestPrice(n, flights, src, dst, K))

easy

A. 500

B. 200

C. -1

D. 100

Solution

1. Step 1: Trace initial heap and first pop

   Heap starts with (0,0,0). Pop (0,0,0), node=0, stops=0 <= K=1, push neighbors: (100,1,1) and (500,2,1).

2. Step 2: Pop next smallest cost

   Pop (100,1,1), node=1, stops=1 <= K=1, push neighbor: (200,2,2). Next pop is (200,2,2) but stops=2 > K, so not pushed further. Then pop (500,2,1), node=2 matches dst, return cost=500. But since (200,2,2) is invalid (stops>1), the first valid arrival at dst is (500,2,1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stops constraint prunes cheaper but invalid path; returns 200 [OK]

Hint: Stops count prunes invalid cheaper paths [OK]

Common Mistakes:

• Returning 500 ignoring cheaper path with too many stops
• Returning -1 assuming no path
• Confusing stops count with edges

2. You are given a directed graph with weighted edges representing travel times between nodes. Starting from a given node, you want to find the minimum time it takes for a signal to reach all other nodes. Which algorithmic approach guarantees finding the shortest travel times in this scenario?

easy

A. Use Dijkstra's algorithm with a priority queue to greedily select the next closest node.

B. Use a greedy algorithm that always picks the edge with the smallest weight regardless of path.

C. Use a simple Breadth-First Search (BFS) assuming all edges have equal weight.

D. Use a Depth-First Search (DFS) with path relaxation to explore all paths.

Solution

1. Step 1: Understand the problem requires shortest paths with weighted edges

   BFS assumes equal edge weights and cannot handle varying weights correctly, so it fails here.

2. Step 2: Identify that Dijkstra's algorithm uses a priority queue to always pick the next closest node, guaranteeing optimal shortest paths in graphs with non-negative weights

   DFS with path relaxation is inefficient and does not guarantee optimality without pruning, and greedy edge picking ignores path costs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dijkstra handles weighted shortest paths optimally [OK]

Hint: Dijkstra handles weighted shortest paths optimally [OK]

Common Mistakes:

• Assuming BFS works for weighted graphs
• Thinking DFS with relaxation is efficient
• Believing greedy edge picking always works

3. Consider the following Python code implementing the Bellman-Ford algorithm for the Network Delay Time problem. Given the input times = [[1,2,1],[2,3,2],[1,3,4]], n = 3, and k = 1, what is the final returned value?

easy

A. 4

B. 3

C. 2

D. -1

Solution

1. Step 1: Initialize distances with dist[1]=0, dist[2]=inf, dist[3]=inf

   After first iteration, relax edges: dist[2]=1 (via 1->2), dist[3]=4 (via 1->3)

2. Step 2: Second iteration relaxes edge 2->3: dist[3] updated to dist[2]+2=3 which is less than 4

   No further updates after this iteration, so loop breaks early

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maximum distance is 3, so return 3 [OK]

Hint: Relax edges repeatedly until no updates or n-1 iterations [OK]

Common Mistakes:

• Not updating dist[3] to 3 after second iteration
• Returning initial max distance 4 instead of updated 3
• Confusing iteration count and stopping early

4. What is the time complexity of the BFS-based valid_tree function for a graph with n nodes and e edges, and why?

medium

A. O(n^2) because BFS explores all pairs of nodes

B. O(n) because edges are always n-1 in a tree

C. O(n + e) because BFS visits each node and edge once

D. O(e log n) due to sorting edges before BFS

Solution

1. Step 1: Analyze BFS traversal

   BFS visits each node once and explores each edge once in adjacency lists.

2. Step 2: Consider edges and nodes

   Time complexity is proportional to number of nodes plus edges, O(n + e).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Standard BFS complexity is O(n + e) [OK]

Hint: BFS complexity depends on nodes plus edges [OK]

Common Mistakes:

• Assuming BFS is O(n^2) due to adjacency matrix
• Confusing sorting cost with BFS traversal

5. What is the time complexity of the BFS-based algorithm to find the maximum area of an island in an m x n grid, where each cell is visited at most once?

medium

A. O((m * n)^2) -- BFS could revisit cells multiple times in worst case

B. O(m + n) -- because BFS visits each row and column once

C. O(m * n) -- each cell is visited once and neighbors checked constant times

D. O(m * n) plus extra O(m * n) space for the visited set

Solution

1. Step 1: Identify BFS visits each cell at most once

   Each cell is enqueued and dequeued once, so total operations proportional to number of cells.

2. Step 2: Each cell checks up to 4 neighbors in constant time

   Neighbor checks are constant per cell, so total is O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear in grid size, no repeated visits [OK]

Hint: Each cell visited once -> O(m*n) time [OK]

Common Mistakes:

• Assuming BFS revisits cells multiple times
• Confusing rows+cols with total cells
• Ignoring constant neighbor checks