Problem Statement

In a town of n people labeled 1 to n:

• There is at most one town judge.
• The town judge trusts nobody.
• Everybody else trusts the town judge.

You are given an array trust where trust[i] = [a, b] means person a trusts person b.

Return the label of the town judge, or -1 if no judge exists.

Example:

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

---

Approach (Single-Array Optimized)

Idea:

• Use a single arraytrustScore[n+1] to track each person’s “trust value”:
  • Subtract 1 if they trust someone (they cannot be judge).
  • Add 1 if someone trusts them.
• At the end, the town judge should have trustScore = n – 1:
  • Trusted by everyone else (n-1)
  • Trusts nobody (no subtraction)

Steps:

1. Initialize an array trustScore of size n + 1.
2. Loop through trust array [a, b]:
   • trustScore[a]-- → a trusts someone → reduces score
   • trustScore[b]++ → b is trusted by someone → increases score
3. Loop through 1 to n:
   • If trustScore[i] == n - 1, return i → judge found
4. If no such person, return -1.

Why it works:

• Judge is trusted by all others → +1 for each trust received
• Judge trusts nobody → no -1 applied
• Only the judge will reach trustScore = n-1.

---

Java Code Solution

public class FindTownJudgeOptimized {

    public static int findJudge(int n, int[][] trust) {
        int[] trustScore = new int[n + 1];

        for (int[] t : trust) {
            int a = t[0], b = t[1];
            trustScore[a]--; // a trusts someone → cannot be judge
            trustScore[b]++; // b is trusted → increases score
        }

        for (int i = 1; i <= n; i++) {
            if (trustScore[i] == n - 1) {
                return i;
            }
        }

        return -1; // No judge found
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] trust = {{1,3},{2,3}};
        int result = findJudge(n, trust);
        System.out.println("Town judge is: " + result); // Output: 3
    }
}

---

Dry Run Example

Input:

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

Step-by-step Execution:

1. Initialize:

trustScore = [0,0,0,0]

2. Process trust pairs:

• [1,3]: trustScore[1]– → -1, trustScore[3]++ → 1
• [2,3]: trustScore[2]– → -1, trustScore[3]++ → 2

Array after processing:

trustScore = [0, -1, -1, 2]

3. Check each person (1 to 3):

• Person 1 → trustScore=-1 → not judge
• Person 2 → trustScore=-1 → not judge
• Person 3 → trustScore=2 → n-1=2 ✅ → judge found

Result: 3

---

Textual Diagram for Understanding

People: 1, 2, 3
Trust relationships: 1→3, 2→3

Initial trustScore: [0,0,0,0]

After processing:
1: -1 (trusts someone)
2: -1 (trusts someone)
3: 2  (trusted by 2 people)

Check trustScore == n-1 → Person 3 → Town judge

---

Complexity Analysis

• Time Complexity: O(n + t)
  • t = number of trust pairs. One pass through trust array + one pass through n people.
• Space Complexity: O(n)
  • Single array of size n+1.