Find the Town Judge

Problem Description

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:

• The town judge trusts nobody.
• Everybody else (except the town judge) trusts the town judge.
• There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that person ai trusts person bi. If the town judge exists, return his label. Otherwise, return -1.

Examples

Constraints

• 1 ≤ n ≤ 1000
• 0 ≤ trust.length ≤ 10⁴
• trust[i].length == 2
• trust[i] are unique
• ai != bi

In-Degree Minus Out-Degree

Model trust as a directed graph. The town judge has in-degree n-1 (everyone trusts them) and out-degree 0 (they trust nobody). Use a single score array: increment score[b] and decrement score[a] for each (a, b) trust pair. The judge’s score is n - 1 - 0 = n - 1. Find the person with score exactly n - 1.

Solution

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] score = new int[n + 1];
        for (int[] t : trust) {
            score[t[0]]--; // trusts someone: not the judge
            score[t[1]]++; // is trusted
        }
        for (int i = 1; i <= n; i++) {
            if (score[i] == n - 1) return i;
        }
        return -1;
    }
}

class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        score = [0] * (n + 1)
        for a, b in trust:
            score[a] -= 1  # trusts someone: not the judge
            score[b] += 1  # is trusted
        for i in range(1, n + 1):
            if score[i] == n - 1:
                return i
        return -1

#include <vector>

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

Complexity Analysis:

• Time Complexity: O(trust.length + n). One pass over trust to build scores, one pass over n people to find the judge.
• Space Complexity: O(n) for the score array.

Where it breaks: when n = 1, the only person is vacuously the judge (0 people need to trust them, 0 trust relationships needed). The score for person 1 stays at 0, and n - 1 = 0, so score[1] == 0 == n - 1 correctly returns 1.

← All Problems