Find the Town Judge | 2 Approaches | Leetcode 997

This is our 35th Video on our Array Playlist.
In this video we will try to solve a very popular Qn "Find the Town Judge" (Leetcode-9797).

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Find the Town Judge
Company Tags : Microsoft, Amazon, Uber

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[sz.]

done using *set* also
but clicking in_deg and out_deg concept is just awesome

[EB-otuu]

all the comments are not enough to praise the effort you put in every video. thanks a lot

[udaytewary]

First maine socha ye gfg wala celebrity problem haa jaisa hi mere ko bhaut similar lga bs difference itna hi tha ki usme zero or ones the aur isme values haa

Lekin wo outdegree aur indegree wala concept bhaut aacha tha bhaiya maja aa gya Jan kr aage graph me kaam a skta haa question solving m

And for that really thankyou bhaiya

[sagarsen]

Thanks for an optimized way I have also tried by brute force, but these way are more optimized 😇

[al]

Contest k solution bhi de diya karo bhaiya

[animesh]

int indegree[n+1];
memset(indegree, 0, sizeof(indegree));
instead of using vector<int> indegree(n+1);
what effect on time complexity and space complexity?

[souravjoshi]

I can sharing my Java version :
public int findJudge(int N, int[][] trust) {
int[] count = new int[N+1];
for (int[] t: trust) {
count[t[0]]--;
count[t[1]]++;
}
for (int i = 1; i <= N; ++i) {
if (count[i] == N - 1) return i;
}
return -1;
}

[prnvsgr]

java - class Solution {
public int findJudge(int n, int[][] trust) {

if( trust == null) return 0;
int[] trusts = new int[n+1];
int[] trustedby = new int[n+1];

for(int[] relation : trust){
trusts[relation[0]]++;
trustedby[relation[1]]++;
}

for(int i = 1; i<n+1;i++){
if(trusts[i]==0 & trustedby[i] == n-1) return i;
}

return -1;
}

}

[VsEdits]

have done using two maps not optimized but yeah
code :
class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
if(n==1)return 1;
unordered_map<int, int>mp;
unordered_map<int, int>mp2;
for(auto &x:trust)
{
mp[x[1]]++;
}
for(auto &x:trust)
{
mp2[x[0]]=x[1];
}
for(auto &x:mp)
{
if(x.second==n-1 && mp2[x.first]==0) return x.first;
}
return -1;
}
};

[shivsakthi]

Mera Like share subscribe sirf apka channel ko 💥😌👏

[sidharthdhiman]

maine topological sorting hi lgaya but maine pura topoglocial queye wala bhi likha and kahi test case phas rehe sir,

[souravjoshi]

Please upload today's Leetcode "Snakes and Ladders"
Waiting

[muskanyadav]

I have one doubt why we take size of both arrays n+1 instead of n. Btw explanation is very good.

[molyoxide]

Bhaiya map of vectors mein vectors kaise daalenge, push_back se ho nhi rha?
For eg: 1->9, 8, 5
2->4, 6, 0
3->5, 6, 2
Iss ko kaise store kare??

[ektuhaso]

Excuse me sir
Sir can't i use stl in placements?

[shubhamsandanshiv]

When are u uploading today's daily problem?

[-BitWiz]

Which app do you use to draw? could you please tell me?

[XKumarVaibhav]

bhai for the test case given output is not 3 but -1, since 1 doesnot trust 2 please consider this

[PriyaPandey-kzrq]

Yaar bhaiyia ye kya hai apne array ke playlist me graphs ke question daal rakhe hai. Acha khasa flow chal rha arrays ka sab bekar ho gaya. If possible graph ke videos graph ke playlist me dal dijiye.

[JJ-tpdd]

Thanks bhai..apki tabiyt thik h? ya cold hua h? Java Solution

class Solution {
public int findJudge(int n, int[][] trust) {
int[] count = new int[n+1];
for(int[] t : trust){
count[t[0]]--;
count[t[1]]++;
}
for(int i = 1; i <= n; i++){
if(count[i] == n-1) return i;
}
return -1;
}
}

In case you are looking for longer version of the solution in Java using HashMap

class Solution {
public int findJudge(int n, int[][] trust) {
if(n == 1 && trust.length == 0) return 1;
Map<Integer, Integer> thoseWhoAreTrusted = new HashMap<>();
Set<Integer> thoseWhoTrust = new HashSet<>();

for(int i = 0; i < trust.length; i++){
thoseWhoAreTrusted.put(trust[i][1], thoseWhoAreTrusted.getOrDefault(trust[i][1], 0)+1);

}

int ans = -1;
for(Map.Entry<Integer, Integer> entry
if(entry.getValue() == n-1)
ans = entry.getKey();
}

if(ans != -1 && !thoseWhoTrust.contains(ans))
return ans;
return -1;
}
}