[/dsa/leetcode]

997 - Find the Town Judge

Tuesday, 8 September 2026

<easy> [problem]

The judge is the one vertex with in-degree n - 1 and out-degree 0, found by counting degrees on a directed edge list.

{graph}

Problem

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:

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

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

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

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

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

Approach

trust gives us the relationship between a and b in a directed sense, a -> b, i.e. a trusts b. By the conditions in the question, the town judge is trusted by everybody except themselves, so they are trusted by n - 1 people, and that is their in-degree. The judge also trusts nobody, so their out-degree is 0. So we are looking for the person with in-degree n - 1 and out-degree 0, and if there is none we return -1.

Two Arrays

We can keep two arrays that count the in-degree and the out-degree, and then match them against the conditions we are given. So iterate over the trust array and increment out[a] and in[b]. Now that we have the in-degrees and out-degrees, if in[i] == n - 1 and out[i] == 0 for some i, then that person is the town judge and we can return i; if nobody qualifies, return -1.

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

        for (const auto& t : trust) {
            out[t[0]]++;
            in[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (in[i] == n - 1 && out[i] == 0) return i;
        }
        return -1;
    }
};
  • time: O(E + n) — one pass over the edges, one pass over the people
  • space: O(n) — the two degree arrays

Single array

The two arrays can be collapsed into one that stores the difference in - out. Every edge a -> b increments arr[b] and decrements arr[a], and we check for n - 1 as before.

arr[i] = in[i] - out[i]  <=  in[i]  <=  n - 1

Nobody trusts themselves, so indegree caps at n - 1 and that is also the ceiling on arr. Reaching the ceiling makes both inequalities tight at once, forcing out[i] == 0 and in[i] == n - 1, which is the outdegree check we appear to have thrown away.

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> score(n + 1, 0);
        for(const auto& t: trust) {
            score[t[0]]--;
            score[t[1]]++;
        }
        for(int i = 1; i < score.size(); i++) {
            if(score[i] == n - 1) return i;
        }
        return -1;
    }
};
  • time: O(E + n) — same two passes as above
  • space: O(n) — one array instead of two
quantinium © 2026