997. Find the Town Judge

Problem Statement:

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(except for 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 the person labeled ai trusts the person labeled bi.

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

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

Constraints:

• 1<=n<=1000 0<=trust.length<=104 trust[i].length==2
• All the pairs of trust are unique.ai!=bi 1<=ai,bi<=n

Solution:
Algorithm:

1. Create two arrays inDegree and outDegree.
2. Traverse the trust array and update the inDegree and outDegree arrays.
3. Traverse the inDegree array and check if the current person is the town judge.
4. If the current person is the town judge, return the current person.
5. If the town judge does not exist, return -1.

Code:

public class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int[] t : trust) {
            outDegree[t[0]]++;
            inDegree[t[1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

Time Complexity:
O(n)O(n) The time complexity is linear, because we traverse the trust array once.

Space Complexity:
O(n)O(n) The space complexity is linear, because we create two arrays of size n+1.