Number of Good Paths - Leetcode 2421 - Python

0:00 - Read the problem
2:45 - Brute Force Explanation
4:15 - Optimal Force Explanation
11:50 - Coding Explanation

leetcode 2421

#neetcode #leetcode #python

[scresat]

This problem makes me want to leave it all behind and live the rest of my life in the Himalayas away from humanity.

[Raymond-Wu]

You've described these as crackhead problems in the past. It'd be funny if you had a playlist for those types of problems as this one definitely belongs in there!

[AR_]

Hey,
I think the self.rank need to initialized with list of 1's.
self.rank = [1] * n

Because otherwise:
self.rank[bRoot] += self.rank[aRoot]
will be just adding 0's. Thus have no efficiency benefit.

[mucle]

You can do a sortof implicit union find using the graph. First make the graph, then when you go through it, if you see a value less than you, remove that node, and update its neighbors to be your neighbors. Then stop when you find a node larger than you

[hackytech]

Thank you so much ♥, I was waiting for you to upload this. Please keep uploading Daily streak problems 🙏🙏🙏🙏🙏🙏🙏🙏🙏

[kuklama]

This is basically how Quake BSP works right?

[sankararao]

why do we even need to find neighbors, If the node has one occurrence. In this case for the node 2 value 2, we don't even need to run union find for the node 2

[yang]

i'm a little confused at 11:20, how is 0->2->3 a good path? the values of the path are 1->2->1, which breaks the second condition of a good path

[bsuyegwiwu]

I don't understand the last part of the code (# For each disjoint set, how many val’s does it contain?), how does it calculate the number of val's in each disjoin set? Can someone please explain to me? Thansk!

[sypher]

I just watch you for logical part and I get it. Thanks for the videos.

[nuamaaniqbal]

Why do we need to traverse the vals in sorted order ? Why is that necessary ? What would not work if we didnt?

[yang]

For anybody attempting this solution in Java, you need to change the rank to 1 instead of 0 otherwise you'll get TLE.

[narendrayadav]

Thanks a ton !! It was really easy to understand !!

[iliadmitriev]

what's the reason to initialize ranks of vetices at UnionFind class with 0's
I think it's a mistake, should be initialized with 1's

[satyajeetdas]

I came up with dfs solution as soon as i saw the question, but the main problem is how i will know to come up with union find algo for this problem.. i mean what is the intuition behind to determine we will use union find. bcoz i have practised a quite a no of graph problem where the intuition to use union find is quite recognizable but here it is out of please let me know the intuition behind @NeetCodeIO

[CostaKazistov]

Highly underrated channel.
This was a top-notch code walkthrough of LC Hard problem.

[podilichaitanyaakhilkumar]

This is a very difficult problem, but you made it easy. Upload more hard problems with all possible approaches. For medium level questions leetcode discuss section is enough to understand, but it is quite difficult to understand hard problems from discuss section. Hence we need video solution for hard problems. Please make videos on hard problems. Thank you.

[rashzh]

Thanks! Please keep making videos on Daily challenges!

[王梦如-ff]

What will happen if I do the unionFind in the opposite order? 3->2->1

[honestreviewlarki]

Can anyone tell me why my code isn't working?
`
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:

l = len(vals)
if len(set(vals)) == l: return l
g = collections.defaultdict(set)
for a, b in edges:
g[a].add(b)
g[b].add(a)
print(g)
self.ans = 0
vis = set()
def dfs(node):
self.ans += 1
vis.add(node)
path = []
for c in g[node]:
if c in vis: continue

if vals[node] >= vals[c]:
path.append(node)
path.append(c)
print(path)
dfs(c)

return self.ans


for i in range(0, l):
dfs(i)
return self.ans
`