hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Find the Town Judge
Problem : 997. Find the Town Judge
Problem Link : leetcode.com/problems/find-the-town-judge/
Companies Asked : Apple, Adobe, Google, Amazon
Approach:
Let us define two arrays, doTrust , and gainTrust. Both of them increase the appearance count.
For each element in trust[i][0] we will increase the doTrust[trust[i][0]] by 1.
And for each element in trust[i][1], we will increase the gainTrust[trust[i][1]] by 1.
Take a look at the condition -
The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
Now, for each number from i = 1 to N, we need to find whose gainTrust[i] = N - 1 and whose doTrust[i] = 0.
Return that index.
If none is found then return -1.
To optimize space usage, we will declare only one array.
And when counting each appearance, for each of the numbers at trust[i][1], we will ban that number from further counting.
Otherwise, we will continue increasing the count.
Now we will do the same from steps 5 ~ 7.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++]
class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
vector<int>gainTrust(n+1, 0);
// vector<bool> haveTrust(n, 0);
for(int i=0; i<trust.size(); i++){
if(gainTrust[trust[i][1]] != -1) gainTrust[trust[i][1]]++;
gainTrust[trust[i][0]] = -1;
}
int ans = -1;
for(int i=1; i<=n; i++){
if(gainTrust[i] == n-1){
if(ans != -1) return -1;
ans = i;
}
}
return ans;
}
};