LeetCode #997 Find the Town Judge Solution & Explanation

LeetCode 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] = [a_i, b_i] representing that the person labeled a_i trusts the person labeled b_i. 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.

Solution

We can use a HashSet to store the people who trust another person, and a dictionary to store the count of how many times each person is trusted by others according to the trust array.

C# Solution

Solution1

public class Solution {
    public int FindJudge(int n, int[][] trust) {
        // If there is only one person in the town, that person must be the judge.
        if(n==1){
            return 1;
        }

        HashSet<int> hSet = new HashSet<int>();    //store the people who trust another one.
        Dictionary<int,int> dict =  new Dictionary<int,int>();  //store the count of trusts for each person.

        foreach(var item in trust){
            hSet.Add(item[0]);
            if (!dict.ContainsKey(item[1]))
            {
                dict.Add(item[1], 1);
            }
            else
            {
                dict[item[1]] = dict[item[1]]+1;
            }
        }

        //Everybody (except for the town judge) trusts the town judge.
        if(hSet.Count!=n-1){    
            return -1;
        }

        // Find the person who is trusted by all others.
        int key = dict.FirstOrDefault(x => x.Value == n-1).Key;
        return key>0 ? key : -1;
    }
}

Conclusion

This feels more like a guessing game for someone’s identity, doesn’t it?

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link: Find the Town Judge – LeetCode

Some Random LeetCode posts