Find the Town Judge - Leetcode 997

Find the Town Judge - Leetcode 997 - Python

Рет қаралды 16,556

Күн бұрын

🚀 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

Пікірлер: 36

@Ezkie 4 ай бұрын

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

@andrews6282 4 ай бұрын

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

@carlosduque5174 4 ай бұрын

Such a big brain solution

@AguirreMoy 4 ай бұрын

🐐

@streambai1045 4 ай бұрын

could you help to give the solution for leetcode 1245 ?

@thiagot7706 4 ай бұрын

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

@tinapineapple 4 ай бұрын

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

@user-cb5xt8lq1y 4 ай бұрын

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 4 ай бұрын

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 4 ай бұрын

What if I use two haspmaps ?

@user-cb5xt8lq1y 4 ай бұрын

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

@akialter 4 ай бұрын

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

@subhajitnaskar6033 4 ай бұрын

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

@user-rv1bx8hx4v 4 ай бұрын

@keremt8727 4 ай бұрын

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 3 ай бұрын

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

@norgzotto 4 ай бұрын

Why was dict chosen? Array is enough.

@kingpen5866 4 ай бұрын

India

@miaowcat1 4 ай бұрын

Cleaner

@NeetCodeIO 4 ай бұрын

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

@Darth_Bateman 4 ай бұрын

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

@Alexander-zt9kz 4 ай бұрын

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 4 ай бұрын

let me get that military discount for the neetcode

@arunvasu30 4 ай бұрын

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

@krityaan 4 ай бұрын

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.

@arunvasu30 4 ай бұрын

@@krityaan thanks man!