I didn't quite understand the concept after I watched this 3 times, so watched ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-ayW5B2W9hfo.html and then came back to this video and totally loved the explanation. Thanks much for uploading.
My collage professor(he actually didn't deserve to br called a professor) did this topic it took him a whole hour long and in the what we got was lots of confusion
Hey, just wondering why at 3:22 you wouldn’t compress all the traversed nodes when finding F to point to G instead, creating a star topology. It seems like this wouldn’t require any more work and would be much more optimal. Sorry to bring this up after so long, haha.
Hi William may I use your source code on github in my video? I'm planning on starting a DSA channel but teaching vietnamese people. Please let me know. Of course I will cite where the code from.
any reason why you use a list and have to worry about/handle an index, when you could just use a stack? and pop from stack to get the ordering? it seems much easier to do without having to code up extra stuff to handle the index.
may be im stupid, but im not quite understand the idea. white, blue, intervals, subintervals. feels like author explain it to himself. not all people understand this, if they not reading Knuth
Note that Singly Linked List also can have Head and Tail Node, But only one pointer to next node. When remove at tail in Singly, We can remove last Node using Tail Node. But Tail Node doesn't know what is previous Node only know next is NULL. So we have to throw away Tail node after removing that.
Extremely good job of explaining! Some people are gifted at teaching! (I know it's not a "gift" it's the result of mainly hard work of looking at problems a zillion times from different perspectives and finding a suitable one to tell the new comer)
Oh how I hate all of you, PHD supremacists, with all your self absorbed big big words, super-scientific encryption from planet Jupiter... "Thiss blue arrow incorporates that triangulation within dissonance of Pythagorean uncertainty of current white arrow that is equilibrium of the cosmic entropy... " Then they are saying why beginners hate any type of science and give up on everything... dude 2 + 2 = 4 that's it ! All this could be simply said is that CURRENT capacity value = [previous capacity (one row above, but same column #) - newer/current given capacity(weight)] add number(value it holds) to newer/current number(value) and that's the value that gets to current cell.....But nooooo it has to go trough rigorous BS
I was having a really hard time with DP but it's so much easier to imagine the solution every dp problem as the shortest paths tree of a directed acyclic graph. so in this case it would follow the topological sort and ONLY update cell (or relax it) if DP's condition is met. In cases of actual graphs this is exactly what we do to find shortest paths tree for a DAG.
Brilliant video, thank you so much for these. I think you could also modify solve() to return a prev collection as in the BFS Shortest Path video, and add the end cell coordinates or marker character ('E') as a parameter to the enclosing function. Then you no longer need all the global counting variables (nodes_left_in_layer etc). You would need to perform [number of steps in shortes path] iterations over prev to get the shortest path and return shortest_path.size() - 1. Maybe not optimal since you have to iterate over the shortest path too, but as long as you still break inside solve() when reached_end = True, the time complexity should stay the same.
None of C++ STL, Java Collections and Python Collections have Indexed Priority Queue. Golang has a 'Fix' method, which allows updating a value, but it does not have an index function to find the value and it's not obvious how to find items after a Fix call, which takes an index as input.
Very clearly explained. You need V-1 times in the worst case. However, if in a round there were no relaxations performed, obviously the next round will also not have any too, so you can stop by detecting the number of relaxations made in a round to be zero.
at 16:45 we are setting low[node] to ids[at] would it not have already happened above when low[at] = min(low[at], low[to]) this seems redundant. what am I missing??
got the case 0 -> [1], 1 -> [0, 2], 2 -> [1] here we have low link value to start will be [0, 1, 2] we start traverse from 0 and dfs to 1. at one we may do either of two ways 1. traverse to 0 then 1 2. traverse to 1 then 0 if it is 1st case then all is good 2 will also get a low link value of 0 in 2nd case 2 is traverse and marked low link value of 1 as 1 has low link value of 1 at that point. 1 will then traverse 0 later and get a low link value of 0 but it will not be propagated to 2 at that point. hence we will need to re assign low link values to stack once we come back to original node which we started with if it’s low link value is itself. to ensure we propagate low value correctly we would have to choose neighbour we already visited first which will increase the time complexity
🎯 Key points for quick navigation: 00:01 *🔑 Explains the union and find operations in a union-find data structure.* 00:17 *📝 Creates a bijective mapping between objects and integers to construct an array-based union-find.* 01:05 *🗃️ Stores the mappings in a hash table for efficient lookup.* 01:34 *📐 Initially, each node in the array points to itself as a root node.* 02:30 *🔗 To unify objects, the smaller component's root node is set as the parent of the larger component's root node.* 04:34 *🧰 Explains the process of merging smaller components into larger ones during unification.* 06:24 *🌳 If two objects belong to the same component, no unification is needed.* 07:42 *🔍 To find the component an element belongs to, follow the parent nodes until reaching the root node.* 08:41 *🚩 The number of components equals the number of remaining root nodes and never increases.* 09:48 *⚡ Path compression, covered in the next video, improves the time complexity of union-find operations.* Made with HARPA AI
