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


  • Approach:

    1. Let us define two arrays, doTrust , and gainTrust. Both of them increase the appearance count.

    2. For each element in trust[i][0] we will increase the doTrust[trust[i][0]] by 1.

    3. And for each element in trust[i][1], we will increase the gainTrust[trust[i][1]] by 1.

    4. Take a look at the condition -

      • The town judge trusts nobody.

      • Everybody (except for the town judge) trusts the town judge.

    5. Now, for each number from i = 1 to N, we need to find whose gainTrust[i] = N - 1 and whose doTrust[i] = 0.

    6. Return that index.

    7. If none is found then return -1.

    8. To optimize space usage, we will declare only one array.

    9. And when counting each appearance, for each of the numbers at trust[i][1], we will ban that number from further counting.

    10. Otherwise, we will continue increasing the count.

    11. 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;

}

};