Find the Town Judge - Leetcode 997 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/find-th...
0:00 - Read the problem
0:35 - Drawing Explanation
6:33 - Coding Explanation
leetcode 997
#neetcode #leetcode #python

[@Ezkie]

This is by far the best explanation I've seen for this problem. Thanks for the help!

[@andrews6282]

Thanks dude! Me being a noob I still look forward to all these solutions 😃

[@carlosduque5174]

Such a big brain solution

[@AguirreMoy]

🐐

[@streambai1045]

could you help to give the solution for leetcode 1245 ?

[@tinapineapple]

hi, can you do a video on 'Best Time to Buy and Sell Stock III' please? Thank you! :)

[@thiagot7706]

What type of solution is this? Some people on solutions tab are marking this one as graph

[@akialter]

HINT: think about incoming edges and outgoing edges of each node

[@user-cb5xt8lq1y]

Instead of using two dictionaries, I've used a single dictionary {i:0 for i in range(1, n+1)} and popped all keys that have outgoing connections while keeping count of incoming connections in the value. Finally I'm left with few keys, which I can check if the corresponding value == (n-1).

[@user-cb5xt8lq1y]

Here's the code:
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
hm = {i:0 for i in range(1, n+1)}
for i in trust:
hm.pop(i[0], None)
if not hm:
return -1
if i[1] not in hm:
continue
else:
hm[i[1]] += 1
for i, j in hm.items():
if j == n - 1:
return i
return -1

[@WillOfHeaven]

What if I use two haspmaps ?

[@user-cb5xt8lq1y]

@@WillOfHeaven You can, but it consumes more memory, and this problem can be further optimised by consuming less memory so why not?

[@user-rv1bx8hx4v]

[@subhajitnaskar6033]

I was trying to get rid of the second loop so did one thing but most of the time I was getting stuck at the case where n = 1 and trust = [] until i changed judge to 1...not sure if this could be an alternative best practices solution
def findJudge(self, n: int, trust: List[List[int]]) -> int:
delta = defaultdict(int)
judge = 1
for elem in range(len(trust)):
delta[trust[elem][0]] -= 1
delta[trust[elem][1]] += 1
if delta[trust[elem][1]] == (n - 1):
judge = trust[elem][1]
if delta[judge] == (n - 1):
return judge
return -1

[@norgzotto]

Why was dict chosen? Array is enough.

[@kingpen5866]

India

[@miaowcat1]

Cleaner

[@NeetCodeIO]

Yeah, I guess I always just use dict because I'm on autopilot.

[@Darth_Bateman]

It’s never a good idea to represent n items with a list.

[@Alexander-zt9kz]

It's the same. When you use an array of size N and access it at some index where said index is either the first or second value of the pair, then its basically the same as using a hashmap of size N where the int key would be the first or second value of the pair.

[@OverrideTips]

let me get that military discount for the neetcode

[@keremt8727]

With the 2nd optimized solution, it might be the case that everybody (including the person himself, that is "i".) trusts the person "i"
By definition, the the town judge doesn't trust himself, so in this case "i" cannot be the town judge as he trusts himself; but the optimized solution would find "i" as the town judge.
An example would be n=2, trust = [[1,2], [2, 2]]; in this case should we not return -1 instead of 2?
But, the 1st solution always returns the correct answer.

[@lavanyam3224]

this test case is invalid, you cannot have [2,2], ie src and dst cannot be the same. Hence his 2nd soln also works

[@Homelander_30]

When you are a beginner where have you learnt all of these.?.

[@krityaan]

It's practice.
You do enough questions, you start seeing patterns.
For example here, just reading the question about relationships between entities points to a graph style question. If you've done enough graph style questions you know about indegrees and outdegrees. You write your own solutions and you get Wrong Answer after Wrong Answer after TLE and come to these videos to see solutions and you learn new tricks (like here I didn't do the delta trick to save memory because it never occurred to me - I also checked if there would be more than one judge even though that isn't possible)
In the end it's doing this process again and again, day after day to build the pattern recognition and the intuitions needed to solve these problems.

[@Homelander_30]

@@krityaan thanks man!

[@spsc07]

yo any idea why this code
class Solution {
public:
int findJudge(int n, vector& trust)
{
int ans=(n*(n+1))/2;
int cmp=0;
for(int i=0;i

[@praveenkumarmadhavarapu]

The judge needs to be trusted by everyone except himself. That’s why -1

[@furkanozbay]

3 is not trusted by "1". But question states; judge needs to be trusted by everyone

[@brodanteyt]

ah I see thanks man!@@furkanozbay