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:
- 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 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 <= N <= 1000
trust.length <= 10000
-
trust[i]
are all different trust[i][0] != trust[i][1]
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
andtrusted
- If a trusts b, then
trustedBy[b] = 1
because b is trusted by a, andtrusted[a] = 1
because a trusted b. For each entry intrust
we populatetrustedBy
andtrusted
. - Then for every people, we see if their
trustedBy
isN-1
and theirtrusted
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).
Top comments (0)