This problem was a huge pain in the ass to explain but I hope this was helpful. If you're unfamiliar with UnionFind you can checkout this video: ruclips.net/video/FXWRE67PLL0/видео.html
can you please explain in the naive solution how to handle the duplicate case? For example: 1->2 == 2->1. It will become difficult if we maintain a set of existing good paths and reverse the current path to check if it exists or not.
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!
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.
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
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!
In a disjoint set, all will have same parent value. ( all nodes in dishoint set will lead to a root after UF). so for eavh val in disjoint set we increment count[parent]
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
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.
1 would work as well. Keep in mind the ranks are only used to compare with each other, so as long as they all have the same starting value it works out.
@@NeetCodeIOYes it works out because the code handles ambiguous situations where the ranks are equal, but the final rank of every node will be 0 if you used your existing code. I encountered a TLE with this solution in java because of it
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)
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 box!!!!! please let me know the intuition behind it!!!!!! @NeetCodeIO
This problem was a huge pain in the ass to explain but I hope this was helpful. If you're unfamiliar with UnionFind you can checkout this video: ruclips.net/video/FXWRE67PLL0/видео.html
thank you NC. I feel like you're sick, Get well soon ❤️
can you please explain in the naive solution how to handle the duplicate case? For example: 1->2 == 2->1. It will become difficult if we maintain a set of existing good paths and reverse the current path to check if it exists or not.
This problem makes me want to leave it all behind and live the rest of my life in the Himalayas away from humanity.
I’m joining you bruh 😔
same bro
Thangod there are others who think same as me for this problem.
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!
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.
Yep, that's correct. My mistake.
I just watch you for logical part and I get it. Thanks for the videos.
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
Thank you so much ♥, I was waiting for you to upload this. Please keep uploading Daily streak problems 🙏🙏🙏🙏🙏🙏🙏🙏🙏
Did the code work for you?
Highly underrated channel.
This was a top-notch code walkthrough of LC Hard problem.
This video is clutch
Thanks a ton !! It was really easy to understand !!
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
I was referring to 1 -> 0 -> 2 -> 4 at that moment.
Awesome JOB!!!!
This is basically how Quake BSP works right?
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!
In a disjoint set, all will have same parent value. ( all nodes in dishoint set will lead to a root after UF).
so for eavh val in disjoint set we increment count[parent]
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
Why do we need to traverse the vals in sorted order ? Why is that necessary ? What would not work if we didnt?
OMG you have a new chaneLL???? nicee
For anybody attempting this solution in Java, you need to change the rank to 1 instead of 0 otherwise you'll get TLE.
Thank you! I was waiting for you to upload this haha
Thanks! Please keep making videos on Daily challenges!
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.
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
1 would work as well. Keep in mind the ranks are only used to compare with each other, so as long as they all have the same starting value it works out.
@@NeetCodeIOYes it works out because the code handles ambiguous situations where the ranks are equal, but the final rank of every node will be 0 if you used your existing code. I encountered a TLE with this solution in java because of it
@@yang5843 Ah, yeah you're right.
What will happen if I do the unionFind in the opposite order? 3->2->1
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
`
Is it TLE or wrong answer?
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 box!!!!! please let me know the intuition behind it!!!!!! @NeetCodeIO