easy Find the Town Judge

Problem Statement

You are given a town with n people, labeled from 1 to n. Some people trust others. You need to find out if there is a "town judge". The town judge is someone who:

Everyone else trusts.
The town judge trusts nobody.

Given n and an array trust, where trust[i] = [a_i, b_i] means person a_i trusts person b_i, return the label of town judge. If there is no town judge, return -1.

Examples

Example 1:

Input: n = 4, trust = [[1, 2], [3, 2], [4, 2]]
Expected Output: 2
Justification: Person 2 is trusted by persons 1, 3, and 4, and person 2 trusts no one. Hence, person 2 is the town judge.

Example 2:

Input: n = 3, trust = [[1, 3], [2, 3]]
Expected Output: 3
Justification: Person 3 is trusted by persons 1 and 2, and person 3 trusts no one. Hence, person 3 is the town judge.

Example 3:

Input: n = 3, trust = [[1, 3], [2, 1], [3, 1]]
Expected Output: -1
Justification: Person 1 is trusted by persons 2 and 3, but person 1 also trusts person 3. Thus, there is no town judge.

Constraints:

1 <= n <= 1000
0 <= trust.length <= 10⁴
trust[i].length == 2
All the pairs of trust are unique.
a_i != b_i
1 <= a_i, b_i <= n

Try it yourself

Try solving this question here:

✅ Solution Find the Town Judge

Problem Statement

You are given a town with n people, labeled from 1 to n. Some people trust others. You need to find out if there is a "town judge". The town judge is someone who:

Everyone else trusts.
The town judge trusts nobody.

Given n and an array trust, where trust[i] = [a_i, b_i] means person a_i trusts person b_i, return the label of town judge. If there is no town judge, return -1.

Examples

Example 1:

Input: n = 4, trust = [[1, 2], [3, 2], [4, 2]]
Expected Output: 2
Justification: Person 2 is trusted by persons 1, 3, and 4, and person 2 trusts no one. Hence, person 2 is the town judge.

Example 2:

Input: n = 3, trust = [[1, 3], [2, 3]]
Expected Output: 3
Justification: Person 3 is trusted by persons 1 and 2, and person 3 trusts no one. Hence, person 3 is the town judge.

Example 3:

Input: n = 3, trust = [[1, 3], [2, 1], [3, 1]]
Expected Output: -1
Justification: Person 1 is trusted by persons 2 and 3, but person 1 also trusts person 3. Thus, there is no town judge.

Constraints:

1 <= n <= 1000
0 <= trust.length <= 10⁴
trust[i].length == 2
All the pairs of trust are unique.
a_i != b_i
1 <= a_i, b_i <= n

Solution

To solve this problem, we can use an approach that involves tracking the trust scores of each person. The idea is to count how many people each person trusts and each person trusted by how many people. If a person is trusted by everyone else and trusts no one, their trust score will reflect that. Specifically, the town judge's trust score should be n - 1, where n is the number of people in the town.

This approach is efficient because it only requires a single pass through the trust array to update the trust scores. Afterward, a single pass through the trust scores is sufficient to identify the town judge. This ensures that the solution works in linear time, making it scalable and effective even for larger inputs.

Step-by-step Algorithm

Initialize an array trustScores of size n + 1 with all elements set to 0.
Iterate through the trust array:
- For each pair [a, b] in trust, decrement trustScores[a] by 1 and increment trustScores[b] by 1. This indicates that person a trusts someone (hence, trustScores[a]--) and person b is trusted by someone (hence, trustScores[b]++).
Check the trust scores:
- Iterate through each person i from 1 to n.
- If trustScores[i] is equal to n - 1, return i as the town judge.
- If no such person is found, return -1.

Algorithm Walkthrough

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

Initialize: trustScores = [0, 0, 0, 0, 0]
Processing trust array:
- Pair [1, 2]: trustScores[1]--, trustScores[2]++ → trustScores = [0, -1, 1, 0, 0]
- Pair [3, 2]: trustScores[3]--, trustScores[2]++ → trustScores = [0, -1, 2, -1, 0]
- Pair [4, 2]: trustScores[4]--, trustScores[2]++ → trustScores = [0, -1, 3, -1, -1]
Check each person:
- Person 1: trustScores[1] = -1
- Person 2: trustScores[2] = 3 (which is equal to n - 1)
- Person 3: trustScores[3] = -1
- Person 4: trustScores[4] = -1
Output: 2

Code

java

class Solution {

  public int findTownJudge(int N, int[][] trust) {
    // If there are less trust pairs than N-1, judge cannot be identified
    if (trust.length < N - 1) {
      return -1;
    }

    // Initialize trustScores array
    int[] trustScores = new int[N + 1];

    // Process trust array to update trustScores
    for (int[] relation : trust) {
      trustScores[relation[0]]--;
      trustScores[relation[1]]++;
    }

    // Identify the town judge
    for (int i = 1; i <= N; i++) {
      if (trustScores[i] == N - 1) {
        return i;
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(
      sol.findTownJudge(4, new int[][] { { 1, 2 }, { 3, 2 }, { 4, 2 } })
    ); // 2
    System.out.println(
      sol.findTownJudge(3, new int[][] { { 1, 3 }, { 2, 3 } })
    ); // 3
    System.out.println(
      sol.findTownJudge(3, new int[][] { { 1, 3 }, { 2, 1 }, { 3, 1 } })
    ); // -1
  }
}

Complexity Analysis

Time Complexity: , where N is the number of people and E is the number of trust relationships. The algorithm iterates through the trust array once to update the trust scores and then through the trustScores array to identify the town judge.
Space Complexity: , where N is the number of people. An additional array trustScores of size N + 1 is used to keep track of the trust scores for each person.

🤖 Don't fully get this? Learn it with Claude

Stuck on Find the Town Judge? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Find the Town Judge** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Find the Town Judge** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Find the Town Judge**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Find the Town Judge**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Graph Traversal - Depth First Sear Find if Path Exists in Graph →