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: kzitem.info/news/bejne/p46NuHlscIJ9f2U
@salim444
Жыл бұрын
thank you NC. I feel like you're sick, Get well soon ❤️
@ankurbose7672
5 ай бұрын
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.
@scresat
Жыл бұрын
This problem makes me want to leave it all behind and live the rest of my life in the Himalayas away from humanity.
@arnabbhattacharya825
Жыл бұрын
I’m joining you bruh 😔
@rajsh3285
Жыл бұрын
same bro
@Engineer_With_A_Life
Жыл бұрын
Thangod there are others who think same as me for this problem.
@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_7333
Жыл бұрын
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.
@NeetCodeIO
Жыл бұрын
Yep, that's correct. My mistake.
@mucle6
Жыл бұрын
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
@sypher4735
Жыл бұрын
I just watch you for logical part and I get it. Thanks for the videos.
@CostaKazistov
Жыл бұрын
Highly underrated channel. This was a top-notch code walkthrough of LC Hard problem.
@hackytech7494
Жыл бұрын
Thank you so much ♥, I was waiting for you to upload this. Please keep uploading Daily streak problems 🙏🙏🙏🙏🙏🙏🙏🙏🙏
@MP-ny3ep
Жыл бұрын
Did the code work for you?
@odysy5179
Жыл бұрын
This video is clutch
@yang5843
Жыл бұрын
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
@NeetCodeIO
Жыл бұрын
I was referring to 1 -> 0 -> 2 -> 4 at that moment.
@narendrayadav71
Жыл бұрын
Thanks a ton !! It was really easy to understand !!
@nuamaaniqbal6373
Жыл бұрын
Why do we need to traverse the vals in sorted order ? Why is that necessary ? What would not work if we didnt?
@yang5843
Жыл бұрын
For anybody attempting this solution in Java, you need to change the rank to 1 instead of 0 otherwise you'll get TLE.
@bittu007ize
Жыл бұрын
Awesome JOB!!!!
@sankararao7563
19 күн бұрын
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
@kuklama0706
5 күн бұрын
This is basically how Quake BSP works right?
@user-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!
@noneyourbussiness5879
4 ай бұрын
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]
@MP-ny3ep
Жыл бұрын
Thank you! I was waiting for you to upload this haha
@alexd627
Жыл бұрын
OMG you have a new chaneLL???? nicee
@podilichaitanyaakhilkumar4911
Жыл бұрын
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.
@rashzh5502
Жыл бұрын
Thanks! Please keep making videos on Daily challenges!
@iliadmitriev01
Жыл бұрын
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
@NeetCodeIO
Жыл бұрын
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.
@yang5843
Жыл бұрын
@@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
@NeetCodeIO
Жыл бұрын
@@yang5843 Ah, yeah you're right.
@王梦如-f5f
Жыл бұрын
What will happen if I do the unionFind in the opposite order? 3->2->1
@satyajeetdas6577
Жыл бұрын
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
@honestreviewlarki3410
Жыл бұрын
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 `
Пікірлер: 39