[LeetCode] Find the Town Judge

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:

• 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:

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: This is a straight forward problem. We can use Hash map to solve this problem. Simply, have a look at the implementation to understand the solution.

Implementation in C#:

    public int FindJudge(int n, int[][] trust)

    {

        if (n == 1 && trust.Length == 0)

        {

            return 1;

        }

        Dictionary<int, List<int>> trustGraph = new Dictionary<int, List<int>>();

        HashSet<int> personsWhoTrust = new HashSet<int>();

        foreach(int[] t in trust)

        {

            if (!trustGraph.ContainsKey(t[1]))

            {

                trustGraph[t[1]] = new List<int>();

            }

            trustGraph[t[1]].Add(t[0]);

            personsWhoTrust.Add(t[0]);

        }

        for (int i = 1; i <= n; ++i)

        {

            if (trustGraph.ContainsKey(i))

            {

                if (trustGraph[i].Count == n - 1 && !personsWhoTrust.Contains(i))

                {

                    return i;

                }

            }

        }

        return -1;

    }

Complexity: O(n)