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.

Examples

Example 1:

1
2
3
4

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

Example 2:

1
2
3
4

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

Example 3:

1
2
3
4

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

Solution

Method 1 – Trust Count and Hash Map

Intuition

The town judge is trusted by everyone else but trusts nobody. We can track how many people trust each person and how many people each person trusts. The judge will be trusted by n-1 people and trust nobody.

Approach

  1. Initialize two arrays or hash maps: one to count how many people trust each person (trusted), and one to count how many people each person trusts (trusts).
  2. For each trust relationship [a, b], increment trusted[b] and trusts[a].
  3. After processing all relationships, check for a person who is trusted by n-1 people and trusts nobody.
  4. Return the label of the judge if found, otherwise return -1.

Complexity

  • ⏰ Time complexity: O(n + m), where n is the number of people and m is the number of trust relationships.
  • 🧺 Space complexity: O(n), for the trust count arrays.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] trusted = new int[n + 1];
        int[] trusts = new int[n + 1];
        for (int[] t : trust) {
            trusts[t[0]]++;
            trusted[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (trusted[i] == n - 1 && trusts[i] == 0) return i;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> trusted(n + 1, 0), trusts(n + 1, 0);
        for (auto& t : trust) {
            trusts[t[0]]++;
            trusted[t[1]]++;
        }
        for (int i = 1; i <= n; ++i) {
            if (trusted[i] == n - 1 && trusts[i] == 0) return i;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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