Find the town judge | Leetcode

[@tejaswigutta9017]

You are a god sent teacher for students like us😻. Can't even imagine what I would have done without this channel.

[@techdose4u]

Thanks bro :) keep enjoying the videos.

[@kushgupta1187]

It can be done using 1 array. For pair a,b = decrement a by 1 and increment b by 1. After loop finishes check if any number has value equal to n-1..if yes return true else false

[@techdose4u]

Nice idea.....

[@kushgupta1187]

@@techdose4u thanks 😊

[@nagajaswanth831]

did it in python using dictionary: class Solution(object): def findJudge(self, N, trust): k=defaultdict(list) for i in trust: k[i[0]].append(i[1]) flag=0 if len(k)==N-1: for i in range(1,N+1): if i not in k: flag=1 nomin=i break if flag==0: return -1 else: return -1 for i in k.keys(): if nomin not in k[i]: return -1 return nomin

[@AmanShukla18031992]

Insert all the people from 1 to N into a map and keep the initial value as 0 Now iterate over the trust vector for every person who trusts another reduce their vote to -1 And for the person, they trust increase there vote by 1 if its current value is not -1 Iterate over the map and get the key with the max value if max value - 1 != N - 1 return -1 else return max values KEY

[@techdose4u]

Yes this is alternate soln :)

[@mayukhchanda5805]

It helped when I visualised this as a graph problem. A pair a,b would mean there is an edge from a->b. In the end we return the one candidate for whom their are n-1 incoming edges and 0 outgoing edges. And since we know a person cannot trust himself(given in constraints) we are sure if some candidate has n-1 edges that means everybody except the person itself trusts him. And if now he also has 0 outgoing edges then we are fine else there is none. This I figured out handles case like :- [[1,3],[2,3],[4,3],[3,4]] for N=4. As you see there are 4 people and everybody trusts 3 but 3 also trusts 4. So there is no town judge.

[@techdose4u]

Graph visualization is good too. But the solution provided also works in all cases. Do you doubt about it?

[@mayukhchanda5805]

@@techdose4u No absolutely not. But it is fun to always know multiple ways to do a tasks. That's why, even after solving a problem I watch your videos, just to find a different approach to the same problem. It helps me to build multiple concepts in case where I get stuck . And I shared my view in that respect. Anyways I didn't mean any offense.

[@ramvigneshganesh4030]

Great video bro, i was thinking this simple solution for an hour, need to practice more, Thank you so much

[@tarushidubey2973]

awesome explanation

[@techdose4u]

Thanks :)

[@Aman-cw8rp]

very well explained 👌👌

[@techdose4u]

Thanks :)

[@anmolwadali9227]

very good approach sir i solved it with maps

[@techdose4u]

Nice....it has same complexity as well.

[@aishwarya1895]

Literally awesome man what an explanation... ✌✌✌✌✌

[@techdose4u]

Thanks

[@sylascoker1483]

Absolutely amazing video, thank you!

[@techdose4u]

Welcome :)

[@beaglesnlove580]

Hey thanks a lot for your help. Your teaching. Is amazing

[@ujjwalbansal2756]

good explanation

[@princeakhil208]

You can use single array to solve this problem and check if n-1 value exit in array

[@techdose4u]

Yes you are correct. We can decrement the value for followers and increment the value for being followed and at the end we can check if some value is N-1. Otherwise we won't have a judge. This idea is good as well.

[@fullysimplified7139]

Amazing video as always :)

[@techdose4u]

Thanks ☺️

[@punjabicodingstyle5111]

I am always in wait for the video.

[@techdose4u]

Wowww...that means you enjoy the content a lot :)

[@punjabicodingstyle5111]

@@techdose4u please sir can you make short video on time complexities?

[@punjabicodingstyle5111]

Yes, it was nice explanation, from last one year i am always looking for best leetcode solutions.

[@anilchaudhry804]

Techdose great one bro 😅

[@techdose4u]

Thanks :)

[@abhishekrai4325]

Thank you so much Sirji 💙

[@techdose4u]

Welcome :)

[@yashCeo]

this looks like some kind of variation of celebrity problem

[@davemustainejigsaw]

Amazing! \m/ Thanks for this, just out of curiosity, this looks like a directed graph, correct?

[@techdose4u]

Thanks. Yes you are correct.

[@thanglexuan8200]

Thanks

[@techdose4u]

Welcome :)

[@deepus9156]

Nice ex[planation

[@techdose4u]

Thanks

[@purendranaik3961]

Hi, I want to take personal guidance. Please let me know what features I can get from it.

[@techdose4u]

Please contact on whatsapp or LinkedIn :)

[@aishwarya1895]

U gained a subscriber

[@techdose4u]

:)

[@safalyaghoshroy2405]

My complexityy is O(vector size) and space O(n). Is it efficient or can more efficient??

[@techdose4u]

It cannot be made more efficient because you need to traverse the array atleast once.

[@sanjay3291]

Thanks!

[@techdose4u]

Welcome :)

[@omkumar_0229]

thank you ,really helpful:)

[@rajeshbammidy180]

O(n) space/Time Using Java:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/Arrays/FindtheTownJudge.java

[@techdose4u]

Thanks Rajesh. You regularly share your code :)

[@rajeshbammidy180]

@@techdose4u Are you using your tab or something to draw(sketch) the things on the screen or you are using your mouse?

[@kundrapuharika6294]

👏👏👏👏👏👏

[@fatimajaffal9843]

I just used two separated vectors rather than pair it doesn't a big deal right? class Solution { public: int findJudge(int N, vector& trust) { vectorv(N+1); vector checked(N+1); for(int i=0;i

[@techdose4u]

It's the same. Whether you use 2 vectors or pair of vector. Time and other complexities are same :)

[@CricVerSe00]

line 12,13 mein can u explain working of .first and .second?

[@techdose4u]

I have taken array of pair. In order to acces first element of pair you use .first and likewise. Please read pair stl.

[@jyothibabusrimanthula2191]

Topological sort whenever get loop that is no judge case

[@punjabicodingstyle5111]

Sir which software you are using to present solution.

[@techdose4u]

Camtasia inkspace

[@anuragsinha5928]

Java Solution using HashMap and Array : it is following similar approach class Solution { public int findJudge(int N, int[][] trust) { int res=-1; if(N==1) return N; int[] t=new int[N]; Map count=new HashMap(); for(int i=0;i

[@anuragsinha5928]

int[] t=new int[N]; --> t denotes if it is trusting somebody

[@JonWoo]

Thats fine but what is the real life use of this algorithm? Why would you want to know which vertex has no outdegress and all indegrees

[@abhinavminocha1894]

Sir, how can I improve my competitive programming skills? Please guide me some steps to build my skills.

[@techdose4u]

For your info: you don't need CP to get placed into big companies. Now if you want to improve on CP, start with contests on leetcode (weekly+biweekly). Don't miss any. When you are able to solve 3 out of 4 questions then you can move to codeforces div-2. This will work fine. Don't directly jump to codeforces or codechef.

[@anisingh7049]

Can anyone explain me what does arr[trust[i][0]] means

[@techdose4u]

This means the person who is trusting and if you make the last zero as 1 then it means the person who is being trusted.

[@sushilmall254]

In Java class Solution { public int findJudge(int N, int[][] trust) { int[][] res=new int[2][N+1]; int row=trust.length; for(int i=0;i

[@MGtvMusic]

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

[@techdose4u]

👍🏼

[@tejaswigutta9017]

Can anyone please tell how to declare an array with pairs in Java?

[@techdose4u]

Please get the code from comment of Rajesh Bammidy.

[@tejaswigutta9017]

Couldn’t find his comment

[@stankafan6688]

bhaiya thnku

[@techdose4u]

Welcome :)

[@blue_jerry]

Anyone with graph approach??

[@techdose4u]

Share your approach bro. I dint think about graph for this question.

[@punjabicodingstyle5111]

I am first viewer

[@techdose4u]

:) And 1st to comment too :D

[@punjabicodingstyle5111]

@@techdose4u exactly first comment

[@kushagrajain2407]

My python solution ``` class Solution: def findJudge(self, N: int, trust: List[List[int]]) -> int: mydict = {} result = 0 for i in range(N+1): mydict[i] = 0 for edge in trust: ##print(edge[0]) ##print(edge[1]) mydict[edge[0]] -= 1 mydict[edge[1]] += 1 for key,val in mydict.items(): if(val == N-1): result = key break else: result = -1 return(result if result != 0 else 1) ```

[@sivaganesh4489]

My solution similar to you. Any suggestions for improvement bro int[] a = new int[n+1]; for(int[] arr : trust){ a[arr[0]] = -1; if(a[arr[1]]!=-1){ ++a[arr[1]]; } } for(int i=1;i

[@techdose4u]

No improvement required for this. Looks fine.