LeetCode 997 - Find the Town Judge

https://leetcode.com/problems/find-the-town-judge/

In a town, there are N people labelled 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 trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return -1.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Note:

1. 1 <= N <= 1000
2. trust.length <= 10000
3. trust[i] are all different
4. trust[i][0] != trust[i][1]
5. 1 <= trust[i][0], trust[i][1] <= N

X. Graph
https://blog.csdn.net/fuxuemingzhu/article/details/87903828
其实这个就是有向图，[a, b]表示从顶点a出发指向顶点b的一条有向边。

所以，题目的意思就是：是否存在且只存在一个顶点，所有的顶点都指向他，但是这个点不指向任何点。用术语来说就是该顶点的入度是N - 1，出度是0.

我们可以使用一个数组存储每个点的入度和出度的差，当某个点的入度和出度的差是N - 1时，代表他是法官，否则不存在。

证明：如果入度和出度的差 = N - 1，又入度、出度 >= 0，那么入度 = N- 1，出度 = 0，满足条件1和2.一旦存在一个点满足条件，那么说明这个点没有出度，所以不存在另一个点的入度是N - 1，满足条件3
https://leetcode.com/problems/find-the-town-judge/discuss/242938/JavaC%2B%2BPython-Directed-Graph

Consider trust as a graph, all pairs are directed edge.
The point with in-degree - out-degree = N - 1 become the judge.

Explanation:
Count the degree, and check at the end.

Time Complexity:
Time O(T + N), space O(N)

Since town judge trusts nobody, can we say thatthe point who has no out-degree and in-degree == N - 1 is the judge?

    public int findJudge(int N, int[][] trust) {
        int[] count = new int[N+1];
        for (int[] t: trust) {
            count[t[0]]--;
            count[t[1]]++;
        }
        for (int i = 1; i <= N; ++i) {
            if (count[i] == N - 1) return i;
        }
        return -1;
    }

https://leetcode.com/problems/find-the-town-judge/discuss/244198/Java-Straight-forward-solution

I used two integer arrays to represent who people trust and who were trusted.
After storing all values into the two arrays just go through those two arrays and find the person with 0 trust person and being trusted by N - 1 people.

Time Complexity: O(N).

public int findJudge(int N, int[][] arr) {
        int[] trust = new int[N];
        int[] trusted = new int[N];
        for(int i = 0; i < arr.length; i++){
            int a = arr[i][0]; 
            int b = arr[i][1];
            trust[a - 1]++;
            trusted[b - 1]++;
        }
        for(int i = 0; i < N; i++){
            if(trust[i] == 0 && trusted[i] == N - 1)
                return i + 1;
        }
        return -1;
    }

X. https://leetcode.com/problems/find-the-town-judge/discuss/242952/C%2B%2B-4-lines-%22Find-the-Celebrity%22

If we are given trust connections as an adjacency matrix (or a hash map), we can use the same algorithm as in the Find the Celebrity problem. Here is solution and explanationsto that problem. This cool technique to quickly find a potential celebrity helps reduce the runtime and memory complexity.

int findJudge(int N, vector<vector<int>>& trust) {
  vector<vector<int>> knows(N + 1, vector<int>(N + 1));
  for (auto &t : trust) knows[t[0]][t[1]] = 1;
  return findCelebrity(N, knows);
}
int findCelebrity(int n, vector<vector<int>>& knows, int i = 1) {
  for (auto j = i + 1; j <= n; ++j) if (knows[i][j]) i = j;
  for (auto j = 1; j < i; ++j) if (knows[i][j]) return -1;
  for (auto j = 1; j <= n; ++j) if (i != j && !knows[j][i]) return -1;
  return i;
}

Complexity Analysis

Note that we analyze the complexity of findCelebrity (without preparation steps).

Time: O(N).
Memory: O(1).