Code Implementation

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        if n == 1 and not trust:
            return 1
        trust_scores = [0] * (n + 1)
        for a, b in trust:
            trust_scores[a] -= 1
            trust_scores[b] += 1
        for i in range(1, n + 1):
            if trust_scores[i] == n - 1:
                return i
        return -1
      

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

class Solution {
    public int findJudge(int n, int[][] trust) {
        if (n == 1 && trust.length == 0) return 1;
        int[] trustScores = new int[n + 1];
        for (int[] t : trust) {
            trustScores[t[0]]--;
            trustScores[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (trustScores[i] == n - 1) return i;
        }
        return -1;
    }
}
      

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

Problem Description

You are given an integer n representing the number of people in a town labeled from 1 to n. There is a list trust where each element is a pair [a, b] meaning person a trusts person b.

The "town judge" is a person who:

• Is trusted by everyone else (i.e., trusted by n-1 people)
• Trusts nobody (does not appear as a "truster" in any pair)

Your task is to find the label of the town judge, or return -1 if the judge does not exist. There is at most one valid judge.

Thought Process

To solve this problem, let's break down the requirements:

• The judge must be trusted by everyone else, so their "trusted by" count should be n-1.
• The judge must trust nobody, so they should not trust anyone (i.e., not appear as a "truster").

A brute-force approach would check each person to see if they are trusted by everyone else and do not trust anyone, but this would be inefficient. Instead, we can use a single array to track both "trusts" and "trusted by" counts for each person, updating as we process the trust list. This optimization allows us to efficiently find the judge in a single pass.

Solution Approach

Let's outline the steps to solve the problem efficiently:

1. Initialize a trust score array:
   • Create an array trustScores of size n+1 (since people are labeled from 1 to n).
   • Each index represents a person. The value at each index will be incremented when someone trusts them, and decremented when they trust someone else.
2. Process the trust relationships:
   • For each pair [a, b] in trust:
   • Decrement trustScores[a] by 1 (since a trusts someone, disqualifying them from being judge).
   • Increment trustScores[b] by 1 (since b is trusted by someone).
3. Identify the judge:
   • After processing, the judge should have a trust score of exactly n-1 (trusted by everyone else, trusts nobody).
   • Scan through the trustScores array for a person with a value of n-1.
   • If such a person exists, return their label. Otherwise, return -1.
4. Special Case:
   • If n == 1 and trust is empty, the only person is the judge by default.

Example Walkthrough

Let's consider n = 3 and trust = [[1,3], [2,3]].

• Initialize trustScores = [0, 0, 0, 0] (index 0 unused).
• Process [1,3]:
  • trustScores[1] -= 1 → trustScores = [0, -1, 0, 0]
  • trustScores[3] += 1 → trustScores = [0, -1, 0, 1]
• Process [2,3]:
  • trustScores[2] -= 1 → trustScores = [0, -1, -1, 1]
  • trustScores[3] += 1 → trustScores = [0, -1, -1, 2]
• Now scan for trustScores[i] == n-1 == 2:
  • trustScores[1] = -1 (not judge)
  • trustScores[2] = -1 (not judge)
  • trustScores[3] = 2 (judge found!)

Time and Space Complexity

Brute-force approach:

• For each person, count how many trust them and whether they trust anyone else. This takes O(n^2) time in the worst case.

• We process each trust relationship once: O(trust.length)
• We scan the trustScores array once: O(n)
• Total time complexity: O(n + trust.length)
• Space complexity: O(n) for the trustScores array

Summary

The key insight is to track both "trusted by" and "trusts" counts in a single array, allowing us to identify the judge in one pass. By incrementing and decrementing trust scores, we efficiently filter out anyone who trusts someone else or isn't trusted by everyone. This elegant solution is simple, fast, and easy to implement in any language.