title
G-46. Disjoint Set | Union by Rank | Union by Size | Path Compression

description
In this video, I have shown you such a code snippet, which can solve any problem on Disjoint Set on any platform. C++ Code Snippet of DS: https://ide.geeksforgeeks.org/392f3f85-cb79-4631-9da2-3dd78e775873 Java Code Snippet of DS: https://ide.geeksforgeeks.org/fde794b7-8b6f-41e8-8efc-0826b3d318e6 C++/Java/Codes and Notes Link: https://takeuforward.org/data-structure/disjoint-set-union-by-rank-union-by-size-path-compression-g-46/ DP Series: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY SDE Sheet: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/ Check out our Website for curated resources: https://www.takeuforward.org/ Our Second Channel: https://www.youtube.com/channel/UCvEKHATlVq84hm1jduTYm8g In case you are thinking to buy courses, please check below: Code "takeuforward" for 15% off at GFG: https://practice.geeksforgeeks.org/courses Code "takeuforward" for 20% off on sys-design: https://get.interviewready.io?_aff=takeuforward Crypto, I use the Wazirx app: https://wazirx.com/invite/xexnpc4u Take 750 rs free Amazon Stock from me: https://indmoney.onelink.me/RmHC/idjex744 Earn 100 rs by making a Grow Account for investing: https://app.groww.in/v3cO/8hu879t0 Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward ---------------------------------------------------------------------------------------------------------------------------

detail
{'title': 'G-46. Disjoint Set | Union by Rank | Union by Size | Path Compression', 'heatmap': [{'end': 608.51, 'start': 504.45, 'weight': 0.713}, {'end': 1826.257, 'start': 1793.016, 'weight': 0.723}, {'end': 2130.216, 'start': 2103.872, 'weight': 0.75}, {'end': 2206.723, 'start': 2149.355, 'weight': 0.871}], 'summary': 'Tutorial covers the importance of mastering the disjoint set data structure in graph series, its relevance in determining components and complexity of dfs or bfs traversal, explaining its use case and functionality in dynamic graphs, showcasing the implementation of disjoint set data structure using union by rank and union by size, and discussing parent relationship and path compression in data structures, achieving a time complexity of o(4α) and ensuring all links are path compressed and pointing to 1.', 'chapters': [{'end': 91.637, 'segs': [{'end': 36.085, 'src': 'embed', 'start': 3.183, 'weight': 0, 'content': [{'end': 4.404, 'text': 'hey, everyone, welcome back to the channel.', 'start': 3.183, 'duration': 1.221}, {'end': 6.425, 'text': 'i hope you guys are doing extremely well.', 'start': 4.404, 'duration': 2.021}, {'end': 13.93, 'text': "so in this video we're going to learn about the most important topic in the graph series, which is the disjoint set data structure.", 'start': 6.425, 'duration': 7.505}, {'end': 21.936, 'text': "it's a very, very important topic why this is commonly asked in almost all interviews and the online assessments as well.", 'start': 13.93, 'duration': 8.006}, {'end': 24.577, 'text': 'so you need to master this topic and in order to master this topic,', 'start': 21.936, 'duration': 2.641}, {'end': 30.521, 'text': "you have to watch this video and all the follow-up problems that i'll be solving in the next part of this graph series.", 'start': 24.577, 'duration': 5.944}, {'end': 36.085, 'text': "so let's understand why is disjoint set data structure used?", 'start': 30.521, 'duration': 5.564}], 'summary': 'Learn about disjoint set data structure, crucial for interviews and online assessments.', 'duration': 32.902, 'max_score': 3.183, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U3183.jpg'}, {'end': 91.637, 'src': 'embed', 'start': 49.172, 'weight': 1, 'content': [{'end': 51.213, 'text': 'First one is this, second one is this.', 'start': 49.172, 'duration': 2.041}, {'end': 58.377, 'text': 'Now, suddenly someone will come up and say hey, does 1 and 5 belong to the same component or not??', 'start': 51.754, 'duration': 6.623}, {'end': 59.558, 'text': 'How will you determine??', 'start': 58.777, 'duration': 0.781}, {'end': 63.279, 'text': "You will pick up one And you'll start a DFS traversal.", 'start': 59.958, 'duration': 3.321}, {'end': 66.159, 'text': '1, 2, 3, 4.', 'start': 63.299, 'duration': 2.86}, {'end': 67.3, 'text': 'And the traversal is complete.', 'start': 66.16, 'duration': 1.14}, {'end': 69.201, 'text': 'You could not find 5.', 'start': 67.68, 'duration': 1.521}, {'end': 76.302, 'text': "Since you could not find 5 in the DFS traversal of 1 in that component, you'll be like they do not belong to the same component.", 'start': 69.201, 'duration': 7.101}, {'end': 79.103, 'text': "You did a DFS traversal and that's the brute force.", 'start': 76.763, 'duration': 2.34}, {'end': 84.224, 'text': 'How much time will the DFS traversal take? N plus E.', 'start': 80.183, 'duration': 4.041}, {'end': 86.645, 'text': "That's the complexity of the DFS or the BFS.", 'start': 84.224, 'duration': 2.421}, {'end': 91.637, 'text': 'takes already discussed this in the previous section of the graph series.', 'start': 87.793, 'duration': 3.844}], 'summary': 'Determining if 1 and 5 belong to the same component using dfs traversal. complexity is n plus e.', 'duration': 42.465, 'max_score': 49.172, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U49172.jpg'}], 'start': 3.183, 'title': 'Disjoint set data structure', 'summary': 'Introduces the importance of mastering the disjoint set data structure in the graph series, commonly asked in interviews and online assessments, due to its relevance in determining components and complexity of dfs or bfs traversal.', 'chapters': [{'end': 91.637, 'start': 3.183, 'title': 'Disjoint set data structure', 'summary': 'Introduces the importance of mastering the disjoint set data structure in the graph series, commonly asked in interviews and online assessments, due to its relevance in determining components and complexity of dfs or bfs traversal.', 'duration': 88.454, 'highlights': ['The disjoint set data structure is crucial for mastering the graph series, as it is commonly asked in interviews and online assessments, and plays a vital role in determining components.', 'The example of identifying if 1 and 5 belong to the same component showcases the importance of disjoint set data structure in efficiently solving such problems.', 'The complexity of DFS or BFS traversal is N plus E, as discussed in the previous section of the graph series.']}], 'duration': 88.454, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U3183.jpg', 'highlights': ['The disjoint set data structure is crucial for mastering the graph series, commonly asked in interviews and online assessments, and plays a vital role in determining components.', 'The example of identifying if 1 and 5 belong to the same component showcases the importance of disjoint set data structure in efficiently solving such problems.', 'The complexity of DFS or BFS traversal is N plus E, as discussed in the previous section of the graph series.']}, {'end': 296.914, 'segs': [{'end': 223.804, 'src': 'embed', 'start': 91.817, 'weight': 0, 'content': [{'end': 94.32, 'text': 'If you do not know DFS or BFS, go back and watch it.', 'start': 91.817, 'duration': 2.503}, {'end': 98.664, 'text': 'So the brute force is going to take a kind of linear time complexity.', 'start': 94.78, 'duration': 3.884}, {'end': 106.111, 'text': "So This is where something like disjoint set comes in and says, hey, I'm going to do the same thing in constant time.", 'start': 99.105, 'duration': 7.006}, {'end': 115.097, 'text': "You ask me, does 1 and 5 belong to the same component? I'm going to tell you in constant time, either a yes or a no.", 'start': 106.532, 'duration': 8.565}, {'end': 118.619, 'text': "That's the use case of disjoint set data structure.", 'start': 115.497, 'duration': 3.122}, {'end': 123.182, 'text': 'And one more thing, it is usually used in dynamic operations.', 'start': 118.879, 'duration': 4.303}, {'end': 130.244, 'text': 'graphs, graphs which keep on changing, graphs which keep on changing their configuration at every moment.', 'start': 123.602, 'duration': 6.642}, {'end': 133.205, 'text': 'what do you mean by exactly changing configuration?', 'start': 130.244, 'duration': 2.961}, {'end': 135.046, 'text': "i'll explain you that in the later part.", 'start': 133.205, 'duration': 1.841}, {'end': 138.187, 'text': 'so disjoint set gives us two options.', 'start': 135.046, 'duration': 3.141}, {'end': 140.348, 'text': 'one is finding the parent.', 'start': 138.187, 'duration': 2.161}, {'end': 146.05, 'text': "that's one of its main functionality, and the other main functionality is union.", 'start': 140.348, 'duration': 5.702}, {'end': 149.011, 'text': 'now this union can be done with two methods.', 'start': 146.05, 'duration': 2.961}, {'end': 153.494, 'text': 'one is rank, other one is size.', 'start': 149.731, 'duration': 3.763}, {'end': 154.874, 'text': "i'll be discussing both of them.", 'start': 153.494, 'duration': 1.38}, {'end': 160.298, 'text': 'but so primarily it gives you two functions fine, parent and union.', 'start': 154.874, 'duration': 5.424}, {'end': 165.301, 'text': 'now i did talk about dynamic graphs, graph changing, configurations.', 'start': 160.298, 'duration': 5.003}, {'end': 167.122, 'text': "so let's understand this now.", 'start': 165.301, 'duration': 1.821}, {'end': 168.804, 'text': 'what do you mean by these things?', 'start': 167.122, 'duration': 1.682}, {'end': 170.825, 'text': 'these are all edges.', 'start': 168.804, 'duration': 2.021}, {'end': 172.266, 'text': "there's an edge between five and six.", 'start': 170.825, 'duration': 1.441}, {'end': 183.068, 'text': 'okay, so initially what we assume is one, two, three, four, five, six, seven.', 'start': 172.266, 'duration': 10.802}, {'end': 184.77, 'text': 'everyone is alone.', 'start': 183.068, 'duration': 1.702}, {'end': 191.217, 'text': 'so initially, before all these edges formation, every node is single, single, right.', 'start': 184.77, 'duration': 6.447}, {'end': 193.139, 'text': 'so you have one, two.', 'start': 191.217, 'duration': 1.922}, {'end': 195.381, 'text': "what it means is i'm asking you to connect one, two.", 'start': 193.139, 'duration': 2.242}, {'end': 199.705, 'text': 'so that is what union does for you.', 'start': 195.962, 'duration': 3.743}, {'end': 203.148, 'text': 'remember this whenever i say connect one, two.', 'start': 199.705, 'duration': 3.443}, {'end': 206.091, 'text': 'union in disjoint set will do it for you.', 'start': 203.148, 'duration': 2.943}, {'end': 213.798, 'text': "we'll talk about, uh, union in details, but as of now know, the higher level of union, union will go and connect.", 'start': 206.091, 'duration': 7.707}, {'end': 215.479, 'text': "so what i'll do is i'll go and connect.", 'start': 213.798, 'duration': 1.681}, {'end': 216.84, 'text': 'okay, done.', 'start': 215.479, 'duration': 1.361}, {'end': 218.521, 'text': 'next two and three.', 'start': 216.84, 'duration': 1.681}, {'end': 219.202, 'text': 'connect two and three.', 'start': 218.521, 'duration': 0.681}, {'end': 220.482, 'text': 'next four and five.', 'start': 219.202, 'duration': 1.28}, {'end': 221.403, 'text': 'connect four and five.', 'start': 220.482, 'duration': 0.921}, {'end': 222.704, 'text': 'next six and seven.', 'start': 221.403, 'duration': 1.301}, {'end': 223.804, 'text': 'connect six and seven.', 'start': 222.704, 'duration': 1.1}], 'summary': 'Disjoint set data structure provides constant time operations for dynamic graphs and offers functions like finding parent and union.', 'duration': 131.987, 'max_score': 91.817, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U91817.jpg'}, {'end': 284.346, 'src': 'embed', 'start': 252.143, 'weight': 4, 'content': [{'end': 252.844, 'text': 'Till this point.', 'start': 252.143, 'duration': 0.701}, {'end': 254.965, 'text': "they're not in the same component.", 'start': 253.484, 'duration': 1.481}, {'end': 256.106, 'text': 'so the answer will be no.', 'start': 254.965, 'duration': 1.141}, {'end': 262.33, 'text': 'so in any stage someone might come up and ask you, because the graph is changing at every step.', 'start': 256.106, 'duration': 6.224}, {'end': 268.455, 'text': 'but i can ask you a question at any step and you should be able to answer that in constant time.', 'start': 262.33, 'duration': 6.125}, {'end': 272.498, 'text': "that is what this joint set will do, and i'll explain you how it does.", 'start': 268.455, 'duration': 4.043}, {'end': 275.72, 'text': "next five and six let's connect five and six.", 'start': 272.498, 'duration': 3.222}, {'end': 277.982, 'text': "next three and seven let's connect three and seven.", 'start': 275.72, 'duration': 2.262}, {'end': 284.346, 'text': 'now, if i ask you the same question does one and four belong to like after performing all the operation?', 'start': 278.582, 'duration': 5.764}], 'summary': 'Explaining constant time complexity of disjoint set in graph operations.', 'duration': 32.203, 'max_score': 252.143, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U252143.jpg'}], 'start': 91.817, 'title': 'Disjoint set data structure and graph connectivity', 'summary': 'Explains the use case and functionality of disjoint set data structure in dynamic graphs, providing constant time complexity for determining component membership and supporting dynamic graph operations. it also discusses the concept of disjoint set union and demonstrates the process of connecting nodes using union, forming edges between nodes and resulting in connected components. additionally, it explains how the graph changes at every step and how the disjoint set data structure efficiently determines the connectivity of components in the graph, allowing constant time for answering queries about component connectivity.', 'chapters': [{'end': 168.804, 'start': 91.817, 'title': 'Disjoint set data structure', 'summary': 'Explains the use case and functionality of disjoint set data structure in dynamic graphs, providing constant time complexity for determining component membership and supporting dynamic graph operations.', 'duration': 76.987, 'highlights': ['Disjoint set provides constant time complexity for determining component membership, offering a more efficient alternative to brute force linear time complexity.', 'Disjoint set is used in dynamic graphs, enabling constant time operations for graphs that undergo continuous configuration changes.', 'The main functionalities of disjoint set are finding the parent and union, which can be implemented using methods such as rank and size.', 'The use case of disjoint set data structure is in providing constant time complexity for determining component membership in dynamic graph operations.']}, {'end': 223.804, 'start': 168.804, 'title': 'Disjoint set union', 'summary': 'Discusses the concept of disjoint set union and demonstrates the process of connecting nodes using union in disjoint set, forming edges between nodes and resulting in connected components.', 'duration': 55, 'highlights': ['The process starts with every node being initially alone, forming a total of 7 single nodes.', 'The concept of union in disjoint set is used to connect nodes, such as connecting 1 and 2, 2 and 3, 4 and 5, and 6 and 7, resulting in the formation of edges and connected components.', 'The higher level of union is demonstrated as it connects nodes to form edges, illustrating the function of union in disjoint set.']}, {'end': 296.914, 'start': 223.804, 'title': 'Graph formation and joint set', 'summary': 'Explains how the graph changes at every step and how the disjoint set data structure efficiently determines the connectivity of components in the graph, allowing constant time for answering queries about component connectivity.', 'duration': 73.11, 'highlights': ['The disjoint set data structure efficiently determines the connectivity of components in the graph, allowing constant time for answering queries about component connectivity.', 'The graph changes at every step, and the disjoint set data structure can answer questions at any step in constant time.']}], 'duration': 205.097, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U91817.jpg', 'highlights': ['Disjoint set provides constant time complexity for determining component membership, offering a more efficient alternative to brute force linear time complexity.', 'Disjoint set is used in dynamic graphs, enabling constant time operations for graphs that undergo continuous configuration changes.', 'The disjoint set data structure efficiently determines the connectivity of components in the graph, allowing constant time for answering queries about component connectivity.', 'The main functionalities of disjoint set are finding the parent and union, which can be implemented using methods such as rank and size.', 'The graph changes at every step, and the disjoint set data structure can answer questions at any step in constant time.', 'The process starts with every node being initially alone, forming a total of 7 single nodes.', 'The concept of union in disjoint set is used to connect nodes, such as connecting 1 and 2, 2 and 3, 4 and 5, and 6 and 7, resulting in the formation of edges and connected components.', 'The higher level of union is demonstrated as it connects nodes to form edges, illustrating the function of union in disjoint set.', 'The use case of disjoint set data structure is in providing constant time complexity for determining component membership in dynamic graph operations.']}, {'end': 774.194, 'segs': [{'end': 343.166, 'src': 'embed', 'start': 316.187, 'weight': 0, 'content': [{'end': 321.391, 'text': 'So in order to implement disjoint set data structure, we can implement union in two ways.', 'start': 316.187, 'duration': 5.204}, {'end': 322.873, 'text': 'One is the rank.', 'start': 321.952, 'duration': 0.921}, {'end': 325.235, 'text': 'The other one is the size.', 'start': 323.293, 'duration': 1.942}, {'end': 327.396, 'text': 'So I can follow two ways of doing it.', 'start': 325.255, 'duration': 2.141}, {'end': 330.439, 'text': "Okay But initially I'll be teaching you the rank.", 'start': 327.536, 'duration': 2.903}, {'end': 331.36, 'text': "I'll be coding you up.", 'start': 330.539, 'duration': 0.821}, {'end': 338.023, 'text': "showing you how to write a clean code so that it can be reused in almost all the problems, and then i'll be teaching you the size one.", 'start': 331.92, 'duration': 6.103}, {'end': 343.166, 'text': 'so the video will be uh, first union by rank, then union by size.', 'start': 338.023, 'duration': 5.143}], 'summary': 'Teaching implementation of disjoint set data structure with union by rank and size.', 'duration': 26.979, 'max_score': 316.187, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U316187.jpg'}, {'end': 386.143, 'src': 'embed', 'start': 358.715, 'weight': 1, 'content': [{'end': 361.556, 'text': 'okay, so the initial configuration is very, very simple.', 'start': 358.715, 'duration': 2.841}, {'end': 366.077, 'text': 'what we do is we assign a rank array with the same size of the number of nodes.', 'start': 361.556, 'duration': 4.521}, {'end': 369.098, 'text': 'since the graph is one based indexing, i start the array from one.', 'start': 366.077, 'duration': 3.021}, {'end': 371.559, 'text': 'so everyone is assigned to zero.', 'start': 369.098, 'duration': 2.461}, {'end': 373.639, 'text': 'okay, so what does rank zero mean?', 'start': 371.559, 'duration': 2.08}, {'end': 376.9, 'text': 'so, if you see this particular node, there is no one beneath it.', 'start': 373.639, 'duration': 3.261}, {'end': 379.801, 'text': 'so it means there is no one beneath it, zero nodes beneath it.', 'start': 376.9, 'duration': 2.901}, {'end': 384.062, 'text': 'but eventually, with the optimizations that we will do, the meaning will change.', 'start': 379.801, 'duration': 4.261}, {'end': 386.143, 'text': "so i'll explain you throughout the course.", 'start': 384.062, 'duration': 2.081}], 'summary': 'Initial configuration assigns rank array with same size as number of nodes, starting from one, everyone is initially assigned zero.', 'duration': 27.428, 'max_score': 358.715, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U358715.jpg'}, {'end': 485.523, 'src': 'embed', 'start': 454.423, 'weight': 2, 'content': [{'end': 457.104, 'text': 'Find rank of ultimate parents, not U and V.', 'start': 454.423, 'duration': 2.681}, {'end': 462.188, 'text': 'Ultimate parents, okay? Now, connect smaller rank.', 'start': 457.104, 'duration': 5.084}, {'end': 465.252, 'text': 'to larger rank.', 'start': 464.292, 'duration': 0.96}, {'end': 471.756, 'text': 'Connect smaller rank to larger rank always.', 'start': 466.613, 'duration': 5.143}, {'end': 475.738, 'text': 'In case of equality, you can connect anyone to anyone.', 'start': 472.516, 'duration': 3.222}, {'end': 477.339, 'text': 'We will explain that as we move.', 'start': 475.858, 'duration': 1.481}, {'end': 478.039, 'text': 'Okay, cool.', 'start': 477.459, 'duration': 0.58}, {'end': 481.14, 'text': "We have understood or I've written the pseudocode.", 'start': 478.379, 'duration': 2.761}, {'end': 485.523, 'text': "Okay, let's now quickly check out the first operation that has been asked for us.", 'start': 481.24, 'duration': 4.283}], 'summary': 'Pseudocode for connecting ultimate parents by rank.', 'duration': 31.1, 'max_score': 454.423, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U454423.jpg'}, {'end': 629.83, 'src': 'heatmap', 'start': 504.45, 'weight': 4, 'content': [{'end': 510.732, 'text': 'so i can see, as of now, the ultimate parent of one is one and the ultimate parent of two is two.', 'start': 504.45, 'duration': 6.282}, {'end': 512.633, 'text': 'is the rank of both?', 'start': 511.352, 'duration': 1.281}, {'end': 515.356, 'text': 'can i say the rank of both is, as of now, zero.', 'start': 512.633, 'duration': 2.723}, {'end': 518.419, 'text': 'if you carefully see both, the ranks are zero.', 'start': 515.356, 'duration': 3.063}, {'end': 523.424, 'text': 'so if they are equal rank, you can actually connect anyone to anyone very, very important.', 'start': 518.419, 'duration': 5.005}, {'end': 525.046, 'text': 'you can go ahead and connect.', 'start': 523.424, 'duration': 1.622}, {'end': 528.489, 'text': 'either you can connect like one here, or either you can connect two.', 'start': 525.046, 'duration': 3.443}, {'end': 529.871, 'text': 'it is completely your choice.', 'start': 528.489, 'duration': 1.382}, {'end': 537.16, 'text': 'so what do you do is you will go ahead and take this two and say can you please connect with, or i can change the color.', 'start': 530.231, 'duration': 6.929}, {'end': 541.085, 'text': "can you please collect, connect with two, and you'll go to that.", 'start': 537.16, 'duration': 3.925}, {'end': 544.409, 'text': 'now, your above parent is one.', 'start': 541.085, 'duration': 3.324}, {'end': 548.416, 'text': 'now, remember, you connected 2 to 1, right?', 'start': 544.409, 'duration': 4.007}, {'end': 551.457, 'text': 'Both of them had same level.', 'start': 548.916, 'duration': 2.541}, {'end': 553.317, 'text': 'Both of them were equal height.', 'start': 551.777, 'duration': 1.54}, {'end': 555.038, 'text': 'They took it and connected.', 'start': 553.757, 'duration': 1.281}, {'end': 556.338, 'text': 'So the height increased.', 'start': 555.098, 'duration': 1.24}, {'end': 560.819, 'text': 'And if the height increased, the rank will also increase by 1.', 'start': 556.778, 'duration': 4.041}, {'end': 562.739, 'text': 'The rank will also increase by 1.', 'start': 560.819, 'duration': 1.92}, {'end': 564.48, 'text': 'Done? Perfect.', 'start': 562.739, 'duration': 1.741}, {'end': 566.3, 'text': 'Next, 2, 3.', 'start': 564.64, 'duration': 1.66}, {'end': 567.961, 'text': 'And this is where again the next thing comes.', 'start': 566.3, 'duration': 1.661}, {'end': 572.442, 'text': "Who is the ultimate parent of 2? Let's see who is the ultimate parent of 2.", 'start': 568.381, 'duration': 4.061}, {'end': 573.262, 'text': "It's 1 over here.", 'start': 572.442, 'duration': 0.82}, {'end': 575.804, 'text': 'and is the one the top guy?', 'start': 574.042, 'duration': 1.762}, {'end': 579.069, 'text': 'it is so the ultimate parent of two is one.', 'start': 575.804, 'duration': 3.265}, {'end': 580.951, 'text': 'who is the ultimate parent of three?', 'start': 579.069, 'duration': 1.882}, {'end': 583.895, 'text': "be itself, what's the rank rank of?", 'start': 580.951, 'duration': 2.944}, {'end': 586.458, 'text': 'uh, this particular one is one.', 'start': 583.895, 'duration': 2.563}, {'end': 587.8, 'text': 'rank of this particular three is three.', 'start': 586.458, 'duration': 1.342}, {'end': 589.201, 'text': 'if you see, one is one.', 'start': 587.8, 'duration': 1.401}, {'end': 590.483, 'text': 'three is zero.', 'start': 589.201, 'duration': 1.282}, {'end': 591.504, 'text': 'sorry, it will be zero.', 'start': 590.483, 'duration': 1.021}, {'end': 593.626, 'text': 'Who is the greater guy? This one.', 'start': 592.205, 'duration': 1.421}, {'end': 596.748, 'text': 'So 3 will come up and get connected to the.', 'start': 593.986, 'duration': 2.762}, {'end': 600.41, 'text': 'The smaller guy comes up and gets connected to the larger one.', 'start': 596.748, 'duration': 3.662}, {'end': 602.751, 'text': 'So 3 is connected to this.', 'start': 600.87, 'duration': 1.881}, {'end': 604.573, 'text': "Now I'll go and erase this.", 'start': 603.252, 'duration': 1.321}, {'end': 608.51, 'text': 'Connected Do I do anything to the ranks? No.', 'start': 605.387, 'duration': 3.123}, {'end': 610.331, 'text': 'You will not do anything to the ranks.', 'start': 608.73, 'duration': 1.601}, {'end': 614.455, 'text': 'Why? Because it still has a height of 1.', 'start': 610.832, 'duration': 3.623}, {'end': 616.456, 'text': 'Because you connected a smaller to the larger.', 'start': 614.455, 'duration': 2.001}, {'end': 618.658, 'text': 'So the larger is not going to increase.', 'start': 616.576, 'duration': 2.082}, {'end': 619.959, 'text': "It's not going to increase.", 'start': 618.878, 'duration': 1.081}, {'end': 621.46, 'text': 'So thereby we keep the same height.', 'start': 620.199, 'duration': 1.261}, {'end': 623.002, 'text': 'Perfect Next.', 'start': 622.021, 'duration': 0.981}, {'end': 624.963, 'text': 'Connect 4 and 5.', 'start': 623.702, 'duration': 1.261}, {'end': 627.969, 'text': 'Who is the ultimate parent of 4? 4.', 'start': 624.963, 'duration': 3.006}, {'end': 629.83, 'text': 'Is the ultimate parent of 5? 5.', 'start': 627.969, 'duration': 1.861}], 'summary': 'The ranks of nodes in the tree are manipulated based on their connections, leading to changes in their heights and ranks.', 'duration': 24.443, 'max_score': 504.45, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U504450.jpg'}, {'end': 688.625, 'src': 'embed', 'start': 658.716, 'weight': 5, 'content': [{'end': 659.857, 'text': 'so what is the next thing?', 'start': 658.716, 'duration': 1.141}, {'end': 661.519, 'text': 'connect six and seven.', 'start': 659.857, 'duration': 1.662}, {'end': 663.62, 'text': 'so ultimate parent of six is six.', 'start': 661.519, 'duration': 2.101}, {'end': 665.382, 'text': 'ultimate parent of seven is seven.', 'start': 663.62, 'duration': 1.762}, {'end': 666.603, 'text': 'the ranks are zero.', 'start': 665.382, 'duration': 1.221}, {'end': 672.628, 'text': "so what you'll do is you'll connect seven to six, you'll update seven's parent to six.", 'start': 666.603, 'duration': 6.025}, {'end': 675.991, 'text': "you'll update the rank of six to one.", 'start': 672.628, 'duration': 3.363}, {'end': 678.454, 'text': 'this is how you can easily connect them.', 'start': 675.991, 'duration': 2.463}, {'end': 680.336, 'text': 'perfect, done so.', 'start': 678.874, 'duration': 1.462}, {'end': 682.458, 'text': 'apparently i can just remove this as well.', 'start': 680.336, 'duration': 2.122}, {'end': 684.761, 'text': 'so as of now, this is where we stand.', 'start': 682.458, 'duration': 2.303}, {'end': 685.762, 'text': "what's the next thing?", 'start': 684.761, 'duration': 1.001}, {'end': 688.625, 'text': 'it says connect five and six.', 'start': 685.762, 'duration': 2.863}], 'summary': 'Connect nodes 6 and 7, updating ranks and parents accordingly. proceed to connect nodes 5 and 6.', 'duration': 29.909, 'max_score': 658.716, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U658716.jpg'}, {'end': 774.194, 'src': 'embed', 'start': 751.453, 'weight': 3, 'content': [{'end': 759.35, 'text': 'why? because you had four, five, you add six, seven, both of the ranks, if you carefully see four and six at a rank one.', 'start': 751.453, 'duration': 7.897}, {'end': 764.131, 'text': 'so since you attached same guys, height will, if you see the height increased.', 'start': 759.35, 'duration': 4.781}, {'end': 767.772, 'text': 'so apparently you go ahead and say the rank to increase by one more.', 'start': 764.131, 'duration': 3.641}, {'end': 768.952, 'text': 'so the rank will be two.', 'start': 767.772, 'duration': 1.18}, {'end': 774.194, 'text': 'so this is where we stand till we have not performed the last step.', 'start': 768.952, 'duration': 5.242}], 'summary': 'Rank increases by one when adding same-height ranks, resulting in a final rank of two.', 'duration': 22.741, 'max_score': 751.453, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U751453.jpg'}], 'start': 296.914, 'title': 'Disjoint set data structure', 'summary': 'Explains the implementation of disjoint set data structure using union by rank and union by size, assigning ranks and parents to nodes, and performing union operations by finding ultimate parents and connecting smaller ranks to larger ranks.', 'chapters': [{'end': 510.732, 'start': 296.914, 'title': 'Disjoint set data structure', 'summary': 'Explains the implementation of disjoint set data structure using union by rank and union by size, assigning ranks and parents to nodes, and performing union operations by finding ultimate parents and connecting smaller ranks to larger ranks.', 'duration': 213.818, 'highlights': ['The chapter explains the implementation of disjoint set data structure using union by rank and union by size, assigning ranks and parents to nodes, and performing union operations by finding ultimate parents and connecting smaller ranks to larger ranks.', 'The initial configuration involves assigning a rank array with the same size of the number of nodes, starting from one and assigning everyone to zero, and a parent array where initially everyone is the parent of himself.', 'The pseudocode for the union of u, v involves finding the ultimate parent of u and v, finding the rank of the ultimate parents, and connecting the smaller rank to the larger rank with the option of connecting anyone to anyone in case of equality.']}, {'end': 774.194, 'start': 511.352, 'title': 'Connecting nodes in a hierarchy', 'summary': 'Discusses the process of connecting nodes in a hierarchy, where the ranks and ultimate parents of the nodes are used to determine the connections, with an emphasis on increasing ranks when connecting nodes of equal height.', 'duration': 262.842, 'highlights': ['When connecting nodes of equal rank, the rank of both nodes increases by 1, as the height also increases.', 'Connecting a smaller ranked node to a larger one does not change the ranks, maintaining the same height.', 'The process involves updating the ultimate parent and rank of the nodes being connected based on their existing ranks and ultimate parents.']}], 'duration': 477.28, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U296914.jpg', 'highlights': ['The chapter explains the implementation of disjoint set data structure using union by rank and union by size, assigning ranks and parents to nodes, and performing union operations by finding ultimate parents and connecting smaller ranks to larger ranks.', 'The initial configuration involves assigning a rank array with the same size of the number of nodes, starting from one and assigning everyone to zero, and a parent array where initially everyone is the parent of himself.', 'The pseudocode for the union of u, v involves finding the ultimate parent of u and v, finding the rank of the ultimate parents, and connecting the smaller rank to the larger rank with the option of connecting anyone to anyone in case of equality.', 'When connecting nodes of equal rank, the rank of both nodes increases by 1, as the height also increases.', 'Connecting a smaller ranked node to a larger one does not change the ranks, maintaining the same height.', 'The process involves updating the ultimate parent and rank of the nodes being connected based on their existing ranks and ultimate parents.']}, {'end': 1431.97, 'segs': [{'end': 829.827, 'src': 'embed', 'start': 803.408, 'weight': 3, 'content': [{'end': 807.07, 'text': "Okay, so since I'm saying find parent will come into picture, let's understand.", 'start': 803.408, 'duration': 3.662}, {'end': 813.134, 'text': "So when I'm saying does 1 and 7 belong to the same component, I look at the parent of 1, it's 1.", 'start': 807.55, 'duration': 5.584}, {'end': 815.776, 'text': 'I look at the parent of 7, it is 6.', 'start': 813.134, 'duration': 2.642}, {'end': 818.077, 'text': "So I'll be like, okay, the parents are different, they are not.", 'start': 815.776, 'duration': 2.301}, {'end': 818.658, 'text': 'But wait.', 'start': 818.297, 'duration': 0.361}, {'end': 820.959, 'text': 'you should not do like this.', 'start': 819.358, 'duration': 1.601}, {'end': 824.182, 'text': 'just imagine you were having a 8 here.', 'start': 820.959, 'duration': 3.223}, {'end': 828.866, 'text': "imagine, right, i'll ask, does 8 and 7 belong to the same component?", 'start': 824.182, 'duration': 4.684}, {'end': 829.827, 'text': 'now something to notice.', 'start': 828.866, 'duration': 0.961}], 'summary': 'Analyzing components by parent-child relationship, considering 1, 7, and 8.', 'duration': 26.419, 'max_score': 803.408, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U803408.jpg'}, {'end': 862.197, 'src': 'embed', 'start': 837.373, 'weight': 2, 'content': [{'end': 845.57, 'text': 'if i ask you, if 8 and 7 belong to the same component, ideally they should, But if you will look at the parent, then 8 would have stored 5,', 'start': 837.373, 'duration': 8.197}, {'end': 847.822, 'text': '7 would have stored 6..', 'start': 845.57, 'duration': 2.252}, {'end': 848.924, 'text': 'Both have different parents.', 'start': 847.822, 'duration': 1.102}, {'end': 851.646, 'text': 'Can you actually tell on the basis of parents?', 'start': 849.524, 'duration': 2.122}, {'end': 855.43, 'text': 'Or do you need the ultimate parent, the top guy, the boss?', 'start': 852.127, 'duration': 3.303}, {'end': 857.953, 'text': 'You need the boss, you need the ultimate parent.', 'start': 855.45, 'duration': 2.503}, {'end': 862.197, 'text': 'So this is why If I am asking you who is the parent of 7.', 'start': 858.434, 'duration': 3.763}], 'summary': 'In a component system, 8 and 7 have different parents, demonstrating the need for the ultimate parent.', 'duration': 24.824, 'max_score': 837.373, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U837373.jpg'}, {'end': 1412.511, 'src': 'embed', 'start': 1381.868, 'weight': 0, 'content': [{'end': 1385.851, 'text': 'always got it, so thereby the time complexity.', 'start': 1381.868, 'duration': 3.983}, {'end': 1390.196, 'text': 'in order to perform the union operation is bigo of four alpha.', 'start': 1385.851, 'duration': 4.345}, {'end': 1394.62, 'text': 'now this four alpha has a huge mathematic derivation which is not required in interviews.', 'start': 1390.196, 'duration': 4.424}, {'end': 1402.144, 'text': "You can say 4 alpha which is as good as constant because the alpha's value is very, very close to 1..", 'start': 1395.02, 'duration': 7.124}, {'end': 1404.486, 'text': 'It is as good as a constant.', 'start': 1402.144, 'duration': 2.342}, {'end': 1407.448, 'text': 'And in order to find parent, it is also 4 alpha.', 'start': 1404.806, 'duration': 2.642}, {'end': 1412.511, 'text': 'So overall, the data structure works in B go of 4 alpha.', 'start': 1407.748, 'duration': 4.763}], 'summary': 'The time complexity for union and find parent operations in the data structure is o(1).', 'duration': 30.643, 'max_score': 1381.868, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1381868.jpg'}], 'start': 774.194, 'title': 'Parent relationship and path compression in data structures', 'summary': 'Discusses understanding parent relationship in data structures, emphasizing the importance of identifying the ultimate parent. it also explains path compression in the union-find data structure, including its impact on time complexity and the resulting structure of the tree, achieving a time complexity of o(4α).', 'chapters': [{'end': 883.351, 'start': 774.194, 'title': 'Understanding parent relationship in data structures', 'summary': 'Discusses the concept of finding parent in data structures to determine if two elements belong to the same component, highlighting the importance of identifying the ultimate parent and not just the immediate parent.', 'duration': 109.157, 'highlights': ['The importance of determining the ultimate parent in data structures to establish if two elements belong to the same component is emphasized, showcasing the significance of looking beyond immediate parents.', 'The concept of finding parent in data structures is explained through examples, such as determining if 1 and 7 belong to the same component by examining their respective parents, highlighting the practical application of the concept.', 'Emphasizing the creation of a different data structure, distinct from a graph, for determining parent relationships in data structures, underlining the unique approach employed in this context.', "The need to consider the ultimate parent, or 'the boss', in establishing if two elements belong to the same component is underscored, offering a clear criterion for identifying component relationships.", 'The process of identifying the ultimate parent in data structures is illustrated through examples, providing a practical understanding of how to determine if elements belong to the same component.']}, {'end': 1431.97, 'start': 883.831, 'title': 'Path compression in union-find data structure', 'summary': 'Explains the concept of path compression in the union-find data structure, highlighting its ability to reduce tree depth, the impact on time complexity, and the resulting structure of the tree, ultimately achieving a time complexity of o(4α).', 'duration': 548.139, 'highlights': ['The union-find data structure utilizes path compression to reduce the depth of the tree, enabling limited traversals when finding a parent, ultimately leading to a time complexity of O(4α).', 'By applying path compression, the tree structure is significantly reduced in size, leading to limited traversals required to find a parent, resulting in a time complexity of O(4α).', 'The path compression technique in the union-find data structure enables the time complexity for the union operation and finding a parent to be O(4α), where α is very close to 1, effectively treated as a constant.']}], 'duration': 657.776, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U774194.jpg', 'highlights': ['The path compression technique in the union-find data structure enables the time complexity for the union operation and finding a parent to be O(4α), where α is very close to 1, effectively treated as a constant.', 'The union-find data structure utilizes path compression to reduce the depth of the tree, enabling limited traversals when finding a parent, ultimately leading to a time complexity of O(4α).', 'The importance of determining the ultimate parent in data structures to establish if two elements belong to the same component is emphasized, showcasing the significance of looking beyond immediate parents.', 'The concept of finding parent in data structures is explained through examples, such as determining if 1 and 7 belong to the same component by examining their respective parents, highlighting the practical application of the concept.']}, {'end': 1939.874, 'segs': [{'end': 1485.546, 'src': 'embed', 'start': 1456.648, 'weight': 3, 'content': [{'end': 1464.816, 'text': 'So basically, what does this mean? If at any moment 1 comes, 1 will be equal to equal to parent of 1 because parent of 1 is himself.', 'start': 1456.648, 'duration': 8.168}, {'end': 1467.238, 'text': "I'll return the parent as 1.", 'start': 1465.236, 'duration': 2.002}, {'end': 1469.119, 'text': "That's the base case because that is where you stop.", 'start': 1467.238, 'duration': 1.881}, {'end': 1479.048, 'text': 'Otherwise, you will be like, can you please return find parent of parent of U.', 'start': 1469.7, 'duration': 9.348}, {'end': 1482.205, 'text': 'What does this mean? Imagine I give you 5.', 'start': 1479.048, 'duration': 3.157}, {'end': 1485.546, 'text': 'What will happen? It will go and say parent of 5.', 'start': 1482.205, 'duration': 3.341}], 'summary': "Explaining a process where 1's parent is 1, with a base case of 1.", 'duration': 28.898, 'max_score': 1456.648, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1456648.jpg'}, {'end': 1597.629, 'src': 'embed', 'start': 1546.022, 'weight': 2, 'content': [{'end': 1547.662, 'text': "Next, you'll also return 1.", 'start': 1546.022, 'duration': 1.64}, {'end': 1549.403, 'text': 'So parent of 5 is equal to 1.', 'start': 1547.662, 'duration': 1.741}, {'end': 1553.464, 'text': 'So everyone in term will assign 1 to it.', 'start': 1549.403, 'duration': 4.061}, {'end': 1565.606, 'text': 'If everyone assigns 1 to it, so automatically all the links will be path compressed and pointing to 1 and all these links will be destroyed.', 'start': 1554.184, 'duration': 11.422}, {'end': 1567.907, 'text': 'Perfect Done.', 'start': 1567.047, 'duration': 0.86}, {'end': 1573.782, 'text': "So I hope you've understood everything about the union by rank and the path compression.", 'start': 1569.841, 'duration': 3.941}, {'end': 1574.742, 'text': "Now it's time to code it up.", 'start': 1573.822, 'duration': 0.92}, {'end': 1583.985, 'text': "So I'll try to create the data structure in a class so that going forward in the upcoming problems we can use that snippet of code to solve almost all the problems.", 'start': 1575.122, 'duration': 8.863}, {'end': 1588.666, 'text': 'So we have a class of this joint set.', 'start': 1584.425, 'duration': 4.241}, {'end': 1589.887, 'text': 'Nothing to worry.', 'start': 1589.346, 'duration': 0.541}, {'end': 1592.207, 'text': "Like don't get worried about a class.", 'start': 1589.967, 'duration': 2.24}, {'end': 1592.787, 'text': 'Very simple.', 'start': 1592.267, 'duration': 0.52}, {'end': 1593.628, 'text': "It's a very simple thing.", 'start': 1592.827, 'duration': 0.801}, {'end': 1597.629, 'text': "What's the initial configuration? Initial configuration required a rank and a parent.", 'start': 1594.128, 'duration': 3.501}], 'summary': 'Implementing union by rank and path compression in class for data structure.', 'duration': 51.607, 'max_score': 1546.022, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1546022.jpg'}, {'end': 1669.529, 'src': 'embed', 'start': 1644.727, 'weight': 5, 'content': [{'end': 1650.097, 'text': "very important to go till n for one base indexing, And it'll be I itself.", 'start': 1644.727, 'duration': 5.37}, {'end': 1652.258, 'text': 'So this is how the constructor will look like.', 'start': 1650.377, 'duration': 1.881}, {'end': 1659.683, 'text': 'Now what does disjoint set give you? It gave you find ultimate parent, right? So this will be the node.', 'start': 1652.558, 'duration': 7.125}, {'end': 1661.924, 'text': 'And for this, you have to find the ultimate parent.', 'start': 1659.783, 'duration': 2.141}, {'end': 1662.985, 'text': 'So we know one thing.', 'start': 1662.244, 'duration': 0.741}, {'end': 1667.968, 'text': 'If node is equal to equal to the parent of node, this is the ultimate parent for sure.', 'start': 1663.065, 'duration': 4.903}, {'end': 1669.529, 'text': 'So you go ahead and return the node.', 'start': 1668.268, 'duration': 1.261}], 'summary': 'Disjoint set finds ultimate parent, using one base indexing.', 'duration': 24.802, 'max_score': 1644.727, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1644727.jpg'}, {'end': 1720.271, 'src': 'embed', 'start': 1689.49, 'weight': 0, 'content': [{'end': 1691.072, 'text': 'I can tell him that this is the parent.', 'start': 1689.49, 'duration': 1.582}, {'end': 1692.753, 'text': 'So this is where the path compression comes in.', 'start': 1691.092, 'duration': 1.661}, {'end': 1694.515, 'text': 'path compression dal.', 'start': 1693.274, 'duration': 1.241}, {'end': 1701.44, 'text': "next, what i'll do is i'll be like okay, void, union by rank is what i need to implement union by rank.", 'start': 1694.515, 'duration': 6.925}, {'end': 1705.443, 'text': "so i'll have node u and node v, which i have to combine.", 'start': 1701.44, 'duration': 4.003}, {'end': 1714.308, 'text': 'so ultimate parent of can say ultimate parent of u will be find ultimate parent of u.', 'start': 1705.443, 'duration': 8.865}, {'end': 1720.271, 'text': 'similarly, you can say ultimate parent of v will be find ultimate parent of v.', 'start': 1714.308, 'duration': 5.963}], 'summary': 'Implementing path compression and union by rank for ultimate parent finding.', 'duration': 30.781, 'max_score': 1689.49, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1689490.jpg'}, {'end': 1840.449, 'src': 'heatmap', 'start': 1793.016, 'weight': 6, 'content': [{'end': 1802.204, 'text': 'u2v is okay as well, and rank of ultimate of u will increase because that is where i am attaching it to.', 'start': 1793.016, 'duration': 9.188}, {'end': 1805.807, 'text': 'we attach to you, so the larger one will grow in size.', 'start': 1802.204, 'duration': 3.603}, {'end': 1806.768, 'text': "so this is what i'll do.", 'start': 1805.807, 'duration': 0.961}, {'end': 1809.149, 'text': "Once I've done this, I can say the unit is done.", 'start': 1807.288, 'duration': 1.861}, {'end': 1811.43, 'text': 'This is how our data structure will look like.', 'start': 1809.509, 'duration': 1.921}, {'end': 1817.073, 'text': "How can we use this snippet of code? So I'll just hard code it to show you how can we use it.", 'start': 1811.75, 'duration': 5.323}, {'end': 1818.253, 'text': "It's pretty simple.", 'start': 1817.533, 'duration': 0.72}, {'end': 1820.054, 'text': 'So you can be like disjoint set DS.', 'start': 1818.293, 'duration': 1.761}, {'end': 1823.395, 'text': 'What is the number of nodes? So in our case, it was one.', 'start': 1820.514, 'duration': 2.881}, {'end': 1826.257, 'text': 'So I can have it as disjoint set of seven.', 'start': 1823.796, 'duration': 2.461}, {'end': 1831.881, 'text': 'so it will call this constructor and have the initial configuration ready for us.', 'start': 1827.077, 'duration': 4.804}, {'end': 1838.748, 'text': "next will be i'll call it union by rank, and the first thing was 1 comma 2, if you remember in our example right.", 'start': 1831.881, 'duration': 6.867}, {'end': 1840.449, 'text': "so we'll have it 1 comma 2..", 'start': 1838.748, 'duration': 1.701}], 'summary': 'Using disjoint set ds, union by rank method, and initial configuration for data structure.', 'duration': 22.156, 'max_score': 1793.016, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1793016.jpg'}], 'start': 1432.41, 'title': 'Disjoint set data structure', 'summary': 'Explains the implementation of disjoint set data structure using path compression and union by rank, with examples and code snippets to illustrate its usage and functionality. it also covers the process of finding the parent of a given node using union by rank and path compression methods, ensuring all links are path compressed and pointing to 1.', 'chapters': [{'end': 1644.727, 'start': 1432.41, 'title': 'Union by rank and path compression', 'summary': 'Explains the process of finding the parent of a given node using the union by rank and path compression methods, with a clear explanation of the recursive process and its impact on the data structure, ensuring all links are path compressed and pointing to 1.', 'duration': 212.317, 'highlights': ['The process of finding the parent of a given node is explained using the union by rank and path compression methods, resulting in all links being path compressed and pointing to 1. This ensures efficient data structure and optimized retrieval of parent nodes.', 'The recursive process of finding parent nodes is demonstrated, illustrating how each function call eventually leads to the base case of returning 1 as the parent, effectively compressing all links to 1 and optimizing the data structure.', 'The implementation of the data structure in a class is discussed, emphasizing the initialization of rank and parent arrays, and the declaration of functions for reusability, ensuring efficient usage in solving various problems.']}, {'end': 1939.874, 'start': 1644.727, 'title': 'Disjoint set data structure', 'summary': 'Explains the implementation of disjoint set data structure using path compression and union by rank, with examples and code snippets to illustrate its usage and functionality.', 'duration': 295.147, 'highlights': ['The constructor for the disjoint set will have a complexity of O(n) for one base indexing.', 'Path compression is implemented to optimize the find operation by storing the ultimate parent for future queries.', 'The union by rank operation optimizes the combination of nodes based on their ranks to achieve a complexity of O(log n).', 'The example demonstrates the usage of the disjoint set data structure with specific node combinations and checks for component belonging.']}], 'duration': 507.464, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1432410.jpg', 'highlights': ['The union by rank operation optimizes the combination of nodes based on their ranks to achieve a complexity of O(log n).', 'Path compression is implemented to optimize the find operation by storing the ultimate parent for future queries.', 'The process of finding the parent of a given node is explained using the union by rank and path compression methods, resulting in all links being path compressed and pointing to 1. This ensures efficient data structure and optimized retrieval of parent nodes.', 'The recursive process of finding parent nodes is demonstrated, illustrating how each function call eventually leads to the base case of returning 1 as the parent, effectively compressing all links to 1 and optimizing the data structure.', 'The implementation of the data structure in a class is discussed, emphasizing the initialization of rank and parent arrays, and the declaration of functions for reusability, ensuring efficient usage in solving various problems.', 'The constructor for the disjoint set will have a complexity of O(n) for one base indexing.', 'The example demonstrates the usage of the disjoint set data structure with specific node combinations and checks for component belonging.']}, {'end': 2526.147, 'segs': [{'end': 2109.698, 'src': 'embed', 'start': 2080.204, 'weight': 0, 'content': [{'end': 2085.79, 'text': 'they will take the similar time that they were taking and only two nodes will take slightly longer time, which is okay.', 'start': 2080.204, 'duration': 5.586}, {'end': 2090.516, 'text': 'this is the reason we attach smaller to larger.', 'start': 2086.371, 'duration': 4.145}, {'end': 2092.078, 'text': 'first, to keep it shrinked.', 'start': 2090.516, 'duration': 1.562}, {'end': 2099.206, 'text': 'second is to make sure that the time taken in finding of the parents is as minimal as possible.', 'start': 2092.078, 'duration': 7.128}, {'end': 2100.408, 'text': 'so you must be thinking striver.', 'start': 2099.206, 'duration': 1.202}, {'end': 2103.872, 'text': "if that's the case, why are we using something like union by rank?", 'start': 2100.408, 'duration': 3.464}, {'end': 2109.698, 'text': "because After path compression it doesn't even give us the height, because the height is distorted after path compression.", 'start': 2103.872, 'duration': 5.826}], 'summary': 'Using smaller to larger attachment to minimize parent finding time, despite slight increase in time for two nodes.', 'duration': 29.494, 'max_score': 2080.204, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U2080204.jpg'}, {'end': 2130.216, 'src': 'heatmap', 'start': 2103.872, 'weight': 0.75, 'content': [{'end': 2109.698, 'text': "because After path compression it doesn't even give us the height, because the height is distorted after path compression.", 'start': 2103.872, 'duration': 5.826}, {'end': 2115.463, 'text': 'Can we use something as size which keeps a track of what is the size of the component? I think we can.', 'start': 2110.459, 'duration': 5.004}, {'end': 2116.424, 'text': 'I think we can.', 'start': 2115.843, 'duration': 0.581}, {'end': 2118.986, 'text': "So, that's what we will be doing.", 'start': 2116.684, 'duration': 2.302}, {'end': 2124.591, 'text': 'Okay So, what I will try to teach you now is union by size.', 'start': 2119.186, 'duration': 5.405}, {'end': 2130.216, 'text': "We know find parent, we know path compression, but instead of rank, we'll be using the union by size.", 'start': 2125.211, 'duration': 5.005}], 'summary': 'Implementing union by size for efficient path compression in data structures.', 'duration': 26.344, 'max_score': 2103.872, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U2103872.jpg'}, {'end': 2206.723, 'src': 'heatmap', 'start': 2149.355, 'weight': 0.871, 'content': [{'end': 2155.819, 'text': 'so everyone is going to be having a size of one and we know one more thing that the parent will be themselves.', 'start': 2149.355, 'duration': 6.464}, {'end': 2157.459, 'text': 'so this is what we take now.', 'start': 2155.819, 'duration': 1.64}, {'end': 2159.12, 'text': 'to start off with very simple.', 'start': 2157.459, 'duration': 1.661}, {'end': 2160.761, 'text': 'we say one comma two.', 'start': 2159.12, 'duration': 1.641}, {'end': 2162.282, 'text': 'we say one has a size of one.', 'start': 2160.761, 'duration': 1.521}, {'end': 2165.324, 'text': 'two also has a size of one, so both are similar size.', 'start': 2162.282, 'duration': 3.042}, {'end': 2166.484, 'text': "so it doesn't matter whom you attach.", 'start': 2165.324, 'duration': 1.16}, {'end': 2169.026, 'text': 'so i go ahead and attach two over here.', 'start': 2166.484, 'duration': 2.542}, {'end': 2175.749, 'text': 'the moment you attach two to one, the size of one will increase to two, because it took a size of one Got attached to it.', 'start': 2169.026, 'duration': 6.723}, {'end': 2176.91, 'text': 'So the size increased by it.', 'start': 2175.769, 'duration': 1.141}, {'end': 2179.091, 'text': 'Okay Next is 2 to 3.', 'start': 2177.13, 'duration': 1.961}, {'end': 2180.331, 'text': 'Very important point to realize.', 'start': 2179.091, 'duration': 1.24}, {'end': 2182.792, 'text': 'Now 1 has a size of 2.', 'start': 2180.751, 'duration': 2.041}, {'end': 2184.933, 'text': 'And remember the parent of 2 is this type.', 'start': 2182.792, 'duration': 2.141}, {'end': 2187.354, 'text': '1 So 1 has a size of 2.', 'start': 2184.953, 'duration': 2.401}, {'end': 2188.615, 'text': 'And 3 has a size of 1.', 'start': 2187.354, 'duration': 1.261}, {'end': 2189.475, 'text': 'So this is the smaller.', 'start': 2188.615, 'duration': 0.86}, {'end': 2192.113, 'text': 'Goes and gets attached to 1.', 'start': 2189.995, 'duration': 2.118}, {'end': 2194.335, 'text': 'So goes and gets attached to 1.', 'start': 2192.113, 'duration': 2.222}, {'end': 2196.476, 'text': 'So the size will again increase by 1.', 'start': 2194.335, 'duration': 2.141}, {'end': 2199.078, 'text': 'Why? Because 3 was the size of 1.', 'start': 2196.476, 'duration': 2.602}, {'end': 2199.738, 'text': 'Perfect Done.', 'start': 2199.078, 'duration': 0.66}, {'end': 2203.16, 'text': 'And 3 will be having a parent of 1.', 'start': 2200.118, 'duration': 3.042}, {'end': 2203.701, 'text': 'This is also done.', 'start': 2203.16, 'duration': 0.541}, {'end': 2205.062, 'text': 'Next is 4 and 5.', 'start': 2203.801, 'duration': 1.261}, {'end': 2206.723, 'text': "So what I'll do is I'll just omit this.", 'start': 2205.062, 'duration': 1.661}], 'summary': 'The sizes of nodes are being increased based on attachments, resulting in a final parent-child hierarchy.', 'duration': 57.368, 'max_score': 2149.355, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U2149355.jpg'}, {'end': 2320.638, 'src': 'embed', 'start': 2291.748, 'weight': 2, 'content': [{'end': 2293.689, 'text': 'The 4 will be having a size of 7.', 'start': 2291.748, 'duration': 1.941}, {'end': 2295.429, 'text': 'So you can keep a track of size.', 'start': 2293.689, 'duration': 1.74}, {'end': 2302.852, 'text': 'And this actually is much more intuitive, you can say, instead of the rank.', 'start': 2295.749, 'duration': 7.103}, {'end': 2305.053, 'text': "I don't find the rank to be that much intuitive.", 'start': 2302.972, 'duration': 2.081}, {'end': 2313.996, 'text': 'But I find this union by size to be much more intuitive than union by rank, because it kind of makes sense where you are storing the size,', 'start': 2305.513, 'duration': 8.483}, {'end': 2315.557, 'text': 'because rank is distorted.', 'start': 2313.996, 'duration': 1.561}, {'end': 2318.758, 'text': "So what I'll do is I'll try to copy the same thing.", 'start': 2316.097, 'duration': 2.661}, {'end': 2320.638, 'text': "So I'll try to copy the same thing.", 'start': 2319.537, 'duration': 1.101}], 'summary': 'Union by size is more intuitive than union by rank for storing size in data structures.', 'duration': 28.89, 'max_score': 2291.748, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U2291748.jpg'}, {'end': 2486.771, 'src': 'embed', 'start': 2455.064, 'weight': 3, 'content': [{'end': 2456.244, 'text': 'yes, not same and same.', 'start': 2455.064, 'duration': 1.18}, {'end': 2463.247, 'text': 'so this is how you can easily create a snippet of code which has union by rank as well as union by size.', 'start': 2456.244, 'duration': 7.003}, {'end': 2464.287, 'text': 'what is the time complexity?', 'start': 2463.247, 'duration': 1.04}, {'end': 2465.248, 'text': 'which one is better?', 'start': 2464.287, 'duration': 0.961}, {'end': 2472.05, 'text': 'both are of the same time complexity, because we are still attaching them, still creating trees, still having the path compression.', 'start': 2465.248, 'duration': 6.802}, {'end': 2476.432, 'text': 'so both of them will take b, go of 4 alpha, which is as good as a constant.', 'start': 2472.05, 'duration': 4.382}, {'end': 2478.066, 'text': "we'll like.", 'start': 2476.432, 'duration': 1.634}, {'end': 2480.308, 'text': 'will the interviewer ask you about for alpha?', 'start': 2478.066, 'duration': 2.242}, {'end': 2483.79, 'text': "no, because it's it has a very, very huge mathematic derivation.", 'start': 2480.308, 'duration': 3.482}, {'end': 2486.771, 'text': 'you can probably google and read about it for interviews.', 'start': 2483.79, 'duration': 2.981}], 'summary': 'Implementing union by rank and size for efficient code. both have time complexity of o(4 alpha), which is equivalent to a constant.', 'duration': 31.707, 'max_score': 2455.064, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U2455064.jpg'}], 'start': 1940.355, 'title': 'Union by rank and size', 'summary': 'Discusses the rationale and implementation of union by rank in graphs, emphasizing the minimization of travel time and the impact on path compression. it also explores the concept of union by size in data structures, comparing its implementation and time complexity with union by rank.', 'chapters': [{'end': 2103.872, 'start': 1940.355, 'title': 'Union by rank in graphs', 'summary': 'Explains the rationale behind connecting smaller to larger in union by rank in graphs, emphasizing the minimization of travel time for finding parents and the impact on path compression, with a specific example demonstrating the efficiency of connecting smaller to larger nodes.', 'duration': 163.517, 'highlights': ['The reason for connecting smaller to larger in union by rank is to minimize the time taken in finding parents, as it reduces the travel time for nodes, ultimately optimizing the process of finding parents and path compression.', 'Connecting larger to smaller increases the height and consequently the travel time for finding parents, as demonstrated by the example of connecting 1, 2 to 3, 4, 5, resulting in longer travel times for nodes.', 'The approach of connecting smaller to larger aims to keep the graph shrinked and ensure minimal time is taken in finding parents for most nodes, contributing to the efficiency of union by rank in graphs.', 'The concept is illustrated by comparing the travel time for nodes when connecting larger to smaller versus connecting smaller to larger, emphasizing the significant impact on travel time and the overall efficiency of the process.']}, {'end': 2526.147, 'start': 2103.872, 'title': 'Union by size in data structures', 'summary': 'Explains the concept of union by size as a method for optimizing the union-find data structure, demonstrating its implementation and comparing it to union by rank, showcasing the time complexity of both methods and emphasizing the importance of understanding the underlying logic and concepts.', 'duration': 422.275, 'highlights': ['Union by size keeps track of the size of the components, updating the size of the component upon attachment, allowing for a more intuitive understanding compared to union by rank.', "The time complexity of both union by size and union by rank is O(4α), which is approximately constant, and the interviewer's focus is on understanding the logic and concepts rather than the mathematical derivation of the time complexity.", 'Emphasizing the importance of using either union by rank or union by size in the implementation of a data structure, but not both together, due to the need for declaring size and potential confusion.']}], 'duration': 585.792, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/aBxjDBC4M1U/pics/aBxjDBC4M1U1940355.jpg', 'highlights': ['The reason for connecting smaller to larger in union by rank is to minimize the time taken in finding parents, optimizing the process of finding parents and path compression.', 'The approach of connecting smaller to larger aims to keep the graph shrinked and ensure minimal time is taken in finding parents for most nodes, contributing to the efficiency of union by rank in graphs.', 'Union by size keeps track of the size of the components, updating the size of the component upon attachment, allowing for a more intuitive understanding compared to union by rank.', "The time complexity of both union by size and union by rank is O(4α), which is approximately constant, and the interviewer's focus is on understanding the logic and concepts rather than the mathematical derivation of the time complexity."]}], 'highlights': ['The disjoint set data structure is crucial for mastering the graph series, commonly asked in interviews and online assessments, and plays a vital role in determining components.', 'The example of identifying if 1 and 5 belong to the same component showcases the importance of disjoint set data structure in efficiently solving such problems.', 'Disjoint set provides constant time complexity for determining component membership, offering a more efficient alternative to brute force linear time complexity.', 'The disjoint set data structure efficiently determines the connectivity of components in the graph, allowing constant time for answering queries about component connectivity.', 'The chapter explains the implementation of disjoint set data structure using union by rank and union by size, assigning ranks and parents to nodes, and performing union operations by finding ultimate parents and connecting smaller ranks to larger ranks.', 'The path compression technique in the union-find data structure enables the time complexity for the union operation and finding a parent to be O(4α), where α is very close to 1, effectively treated as a constant.', 'The union by rank operation optimizes the combination of nodes based on their ranks to achieve a complexity of O(log n).', 'The process of finding the parent of a given node is explained using the union by rank and path compression methods, resulting in all links being path compressed and pointing to 1. This ensures efficient data structure and optimized retrieval of parent nodes.', 'The reason for connecting smaller to larger in union by rank is to minimize the time taken in finding parents, optimizing the process of finding parents and path compression.']}