Skip to main content
CodePeetCodePeet
CodePeet 250

Find the Town Judge

EASYProblemSolveExternal Links

Description

In a town, there are n people labeled from 1 to n. A rumor suggests that one of them is secretly the town judge. The town judge, if they exist, has two defining properties:

  1. The judge trusts nobody — they have zero outgoing trust relationships.
  2. Everybody else trusts the judge — all other n - 1 people trust the judge.

You are given a number n (the total number of people) and an array trust where each entry trust[i] = [a, b] means that person a trusts person b. Trust is one-directional: if person a trusts person b, it does not mean person b trusts person a.

Return the label of the town judge if they exist. If no person satisfies both conditions, return -1.

Examples

Example 1

Input: n = 2, trust = [[1, 2]]

Output: 2

Explanation: There are 2 people. Person 1 trusts person 2 (indicated by the edge [1, 2]). Person 2 does not appear as the first element in any trust pair, so person 2 trusts nobody — condition 1 is satisfied. Person 2 is trusted by person 1 (the only other person), so condition 2 is also satisfied. Person 2 is the town judge.

Example 2

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

Output: 3

Explanation: Person 1 trusts person 3 and person 2 trusts person 3. Person 3 does not trust anyone (no [3, x] entries exist). Person 3 is trusted by both person 1 and person 2, which is all n - 1 = 2 other people. Person 3 is the town judge.

Example 3

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

Output: -1

Explanation: Person 3 is trusted by persons 1 and 2, but person 3 also trusts person 1 (edge [3, 1]). Since the judge must trust nobody, person 3 fails condition 1. No other person is trusted by everyone else either: person 1 is only trusted by person 3, and person 2 is not trusted by anyone. There is no town judge.

Constraints

  • 1 ≤ n ≤ 1000
  • 0 ≤ trust.length ≤ 10^4
  • trust[i].length == 2
  • All the pairs of trust are unique
  • a_i ≠ b_i
  • 1 ≤ a_i, b_i ≤ n

Editorial

Brute Force

Intuition

The most straightforward approach is to try each person as a potential judge and verify both conditions for them.

Imagine you are a detective interviewing townspeople. For each suspect, you check two things: (1) Does this person trust anyone? You go through every trust record looking for an entry where this person is the truster. If you find even one, they cannot be the judge. (2) Does everyone else trust this person? You go through every trust record again, counting how many people trust this suspect. If the count equals n - 1 (everyone else), they are the judge.

This approach is simple and direct: for each of the n people, we scan the entire trust array up to twice — once to check if they trust someone, and once to count how many people trust them. If any person passes both checks, they are the judge.

Step-by-Step Explanation

Let's trace through with n = 3, trust = [[1, 3], [2, 3]]:

Step 1: Consider person 1 as the judge candidate.

Step 2: Scan the trust array for any entry [1, x]: found [1, 3]. Person 1 trusts person 3. Since the judge must trust nobody, person 1 fails condition 1 immediately. Not the judge.

Step 3: Consider person 2 as the judge candidate.

Step 4: Scan the trust array for any entry [2, x]: found [2, 3]. Person 2 trusts person 3. Condition 1 fails. Not the judge.

Step 5: Consider person 3 as the judge candidate.

Step 6: Scan the trust array for any entry [3, x]: no entries found! Person 3 trusts nobody. Condition 1 passes ✓.

Step 7: Now check condition 2: count entries [x, 3] in the trust array. Found [1, 3] and [2, 3] — that's 2 people trusting person 3. Since n - 1 = 2, condition 2 passes ✓.

Step 8: Both conditions met. Person 3 is the town judge! Return 3.

Brute Force — Testing Each Person as Judge Candidate — Watch how we test each person one by one, scanning the trust array to check if they trust nobody and are trusted by everyone else.

Algorithm

  1. For each person candidate from 1 to n:
    a. Scan the trust array to check if any entry [candidate, x] exists
    • If found, this person trusts someone → skip to the next candidate
      b. If no such entry exists (trusts nobody), scan the trust array again to count entries [x, candidate]
    • If the count equals n - 1, this person is the judge → return candidate
  2. If no person passes both checks, return -1

Code

class Solution {
public:
    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;
    }
};
class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        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
class Solution {
    public 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;
    }
}

Complexity Analysis

Time Complexity: O(n × E)

For each of the n people, we scan the trust array (of length E) up to twice: once to check if they trust someone, and once to count how many people trust them. In the worst case, this gives n × 2E = O(n × E) operations.

With n ≤ 1000 and E ≤ 10^4, the worst case is about 1000 × 10,000 = 10^7 operations. This is borderline for typical time limits and could be slow for the upper constraint values.

Space Complexity: O(1)

We use only a few scalar variables (candidate, trustedByCount, trustsSomeone). No additional data structures grow with the input size.

Why This Approach Is Not Efficient

The brute force re-scans the entire trust array for each candidate person. This means the same trust edges are examined over and over — once per candidate. If we have 1000 people and 10,000 trust edges, we perform up to 10 million edge inspections.

The fundamental inefficiency is that we are computing the same information redundantly. For each person, we want to know (a) how many people they trust and (b) how many people trust them. These are simply the out-degree and in-degree of each node in the trust graph.

Key insight: instead of recomputing degrees from scratch for each candidate, we can pre-compute all degrees in a single pass through the trust array. Building two arrays — one for out-degrees and one for in-degrees — takes just O(E) time. Then finding the person with out-degree 0 and in-degree n-1 takes O(n) time. Total: O(E + n) instead of O(n × E).

For n = 1000 and E = 10,000:

  • Brute force: up to 10,000,000 operations
  • Degree counting: about 11,000 operations

That's nearly a 1000× improvement.

Optimal Approach - In-Degree and Out-Degree Counting

Intuition

Think of the trust relationships as a directed graph: each person is a node, and each trust entry [a, b] is a directed edge from node a to node b. In this graph model, the town judge has a very distinctive signature:

  • Out-degree = 0: The judge has no outgoing edges (trusts nobody)
  • In-degree = n - 1: The judge receives edges from every other person (everyone trusts the judge)

No other person can have this exact combination. Someone who is trusted by everyone but also trusts one person would have in-degree n-1 but out-degree ≥ 1 — they fail condition 1.

Instead of building an actual graph, we can capture all the information we need with just two simple counting arrays: one tracking how many people each person trusts (out-degree), and one tracking how many people trust each person (in-degree). A single pass through the trust array fills both arrays, and then a single scan of all n people finds the one matching the judge's signature.

Directed graph showing trust relationships: nodes 1, 2, 3 with edges 1→3 and 2→3, node 3 highlighted as the judge
Directed graph showing trust relationships: nodes 1, 2, 3 with edges 1→3 and 2→3, node 3 highlighted as the judge

Step-by-Step Explanation

Let's trace through with n = 3, trust = [[1, 3], [2, 3]]:

Step 1: Initialize two arrays of size n + 1 = 4 (index 0 unused): out_degree = [0, 0, 0, 0] and in_degree = [0, 0, 0, 0]. Indices 1-3 correspond to persons 1-3.

Step 2: Process trust[0] = [1, 3]: person 1 trusts person 3. Increment out_degree[1] from 0 to 1 (person 1 now trusts 1 person) and in_degree[3] from 0 to 1 (person 3 is now trusted by 1 person). out_degree = [, 1, 0, 0], in_degree = [, 0, 0, 1].

Step 3: Process trust[1] = [2, 3]: person 2 trusts person 3. Increment out_degree[2] from 0 to 1 and in_degree[3] from 1 to 2. out_degree = [, 1, 1, 0], in_degree = [, 0, 0, 2]. All edges processed.

Step 4: Now scan each person for the judge signature (out_degree = 0 AND in_degree = n - 1 = 2). Check person 1: out_degree[1] = 1 ≠ 0. Person 1 trusts someone — not the judge.

Step 5: Check person 2: out_degree[2] = 1 ≠ 0. Person 2 also trusts someone — not the judge.

Step 6: Check person 3: out_degree[3] = 0 ✓ (trusts nobody) and in_degree[3] = 2 = n - 1 ✓ (trusted by everyone else). Both conditions satisfied!

Step 7: Return 3 — person 3 is the town judge. Found in one pass through the trust array plus one scan of all people.

Degree Counting — Build and Scan in Linear Time — Watch how we build out-degree and in-degree arrays in a single pass through trust edges, then scan to find the person with out-degree 0 and in-degree n-1.

Algorithm

  1. Create two arrays of size n + 1 (to use 1-based indexing): out_degree and in_degree, both initialized to zero
  2. For each trust relationship [a, b]:
    • Increment out_degree[a] by 1 (person a trusts someone)
    • Increment in_degree[b] by 1 (person b is trusted by someone)
  3. For each person i from 1 to n:
    • If out_degree[i] == 0 AND in_degree[i] == n - 1, return i (this person is the judge)
  4. If no person satisfies both conditions, return -1

Code

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> outDegree(n + 1, 0);
        vector<int> inDegree(n + 1, 0);

        for (auto& t : trust) {
            outDegree[t[0]]++;
            inDegree[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (outDegree[i] == 0 && inDegree[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
};
class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        out_degree = [0] * (n + 1)
        in_degree = [0] * (n + 1)

        for a, b in trust:
            out_degree[a] += 1
            in_degree[b] += 1

        for person in range(1, n + 1):
            if out_degree[person] == 0 and in_degree[person] == n - 1:
                return person

        return -1
class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] outDegree = new int[n + 1];
        int[] inDegree = new int[n + 1];

        for (int[] t : trust) {
            outDegree[t[0]]++;
            inDegree[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (outDegree[i] == 0 && inDegree[i] == n - 1) {
                return i;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(E + n)

We make one pass through the trust array to build the degree counts — this takes O(E) time where E = trust.length. Then we scan all n people once to find the judge — O(n) time. Total: O(E + n).

With E ≤ 10^4 and n ≤ 1000, the worst case is about 11,000 operations. This is extremely efficient and well within time limits.

Space Complexity: O(n)

We use two arrays of size n + 1 to store the in-degree and out-degree counts. Each array uses O(n) space, so the total additional space is O(n). This is a worthwhile trade-off: we spend O(n) extra memory to avoid O(n × E) redundant computations.