LeetCode: Find the Town Judge

Problem Statement

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

Solution

class Solution {
public:
    int findJudge(int N, vector<vector<int>>& trust) {
        unordered_map<int,int>trustedBy, trusted;

        int judge = -1;
        for(int i=1;i<=N;i++)
        {
            trustedBy[i]=0;
            trusted[i]=0;
        }
        for(int i=0;i<trust.size();i++)
        {
            trustedBy[trust[i][1]]++;
            trusted[trust[i][0]]++;
        }
        for(int i=1;i<=N;i++)
        {
            if(trustedBy[i] == N-1 && trusted[i] == 0)
            {
                judge = i;
                break;
            }
        }
        return judge;
    }
};

Solution Thought Process

• First we declare two unordered_maps - trustedBy and trusted
• If a trusts b, then trustedBy[b] = 1 because b is trusted by a, and trusted[a] = 1 because a trusted b. For each entry in trust we populate trustedBy and trusted.
• Then for every people, we see if their trustedBy is N-1 and their trusted is 0, meaning that they have been trusted by all and they didn't trust anyone. If we found anyone like this, we break the loop and set the people as our judge.

Complexity

Time Complexity: O(n).

Space Complexity: O(n).