Find the Town Judge

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 trust, an array of pairs trust[i] = [a, b] representing that the person labeled a trusts the person labeled b.

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

Example 1:

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

Approach

Java

public class FindTownJudge {
    public static void main(String[] args) {
        int N = 3;
        int[][] trust = { { 1, 3 }, { 2, 3 } };
        System.out.println(findJudge(N, trust));
    }

    static int findJudge(int N, int[][] trust) {
        int indegree[] = new int[N + 1];
        int[] trusty = new int[N + 1];
        for (int[] e : trust) {
            int a = e[0];
            int b = e[1];
            // update indegree
            indegree[b]++;
            trusty[a] = 1;
        }
        for (int i = 1; i <= N; i++) {
            if (trusty[i] == 0 && indegree[i] == N - 1)
                return i;
        }
        return -1;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int findJudge(int N, vector<vector<int>> &trust)
{
    vector<int> indegree(N + 1);
    vector<bool> trusty(N + 1);
    for (vector<int> e : trust)
    {
        int a = e[0];
        int b = e[1];

        //update indegree
        indegree[b]++;
        trusty[a] = true;
    }
    for (int i = 1; i <= N; i++)
    {
        if (!trusty[i] && indegree[i] == N - 1)
            return i;
    }
    return -1;
}

int main()
{
    int N = 3;
    vector<vector<int>> trust = {{1, 3}, {2, 3}};
    cout << findJudge(N, trust);
    return 0;
}