title
G-16. Number of Distinct Islands | Constructive Thinking + DFS | C++ | Java

description
GfG-Problem Link: https://bit.ly/3AsA08W C++/Java/Codes and Notes Link: Soon 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-16. Number of Distinct Islands | Constructive Thinking + DFS | C++ | Java', 'heatmap': [{'end': 991.637, 'start': 950.312, 'weight': 0.743}, {'end': 1061.759, 'start': 1014.857, 'weight': 0.706}], 'summary': 'Discusses the problem of finding the number of distinct islands in a boolean 2d matrix, emphasizing the use of bfs or dfs for consistent traversal order, and efficient tracking and counting using sets and vectors. it also covers the algorithm for grid traversal and dfs implementation, highlighting constraints and complexities.', 'chapters': [{'end': 433.091, 'segs': [{'end': 39.311, 'src': 'embed', 'start': 16.454, 'weight': 0, 'content': [{'end': 25.458, 'text': 'you have to find the number of distinct islands where a group of connected ones form an island again very important to notice horizontally or vertically.', 'start': 16.454, 'duration': 9.004}, {'end': 27.859, 'text': 'that means only these directions are allowed.', 'start': 25.458, 'duration': 2.401}, {'end': 38.15, 'text': 'uh, two islands are considered to be distinct if, and only if, one island is equal to the another, not rotated or reflected.', 'start': 28.679, 'duration': 9.471}, {'end': 39.311, 'text': 'let me explain you.', 'start': 38.15, 'duration': 1.161}], 'summary': 'Find number of distinct islands based on connected ones.', 'duration': 22.857, 'max_score': 16.454, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo16454.jpg'}, {'end': 169.157, 'src': 'embed', 'start': 141.061, 'weight': 3, 'content': [{'end': 145.843, 'text': 'now, one of the things you can say is you can store this shape.', 'start': 141.061, 'duration': 4.782}, {'end': 158.868, 'text': 'yes, you can store this shape the shape, the shape, the shape in some set data structure, and then set will say how many unique are there?', 'start': 145.843, 'duration': 13.025}, {'end': 161.369, 'text': 'how many unique are there?', 'start': 158.868, 'duration': 2.501}, {'end': 163.27, 'text': 'because set does that for you.', 'start': 161.369, 'duration': 1.901}, {'end': 169.157, 'text': 'but how do i store this shape is my question.', 'start': 163.27, 'duration': 5.887}], 'summary': 'Storing the shape in a set data structure to find unique elements.', 'duration': 28.096, 'max_score': 141.061, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo141061.jpg'}, {'end': 368.256, 'src': 'embed', 'start': 337.211, 'weight': 5, 'content': [{'end': 341.016, 'text': 'But over here, when you subtract the base, you get these things.', 'start': 337.211, 'duration': 3.805}, {'end': 342.359, 'text': 'You get these things.', 'start': 341.437, 'duration': 0.922}, {'end': 346.124, 'text': 'Let me give you one more example to have these things in clarity.', 'start': 342.859, 'duration': 3.265}, {'end': 347.566, 'text': "Let's see the next.", 'start': 346.865, 'duration': 0.701}, {'end': 350.511, 'text': 'identical set.', 'start': 348.931, 'duration': 1.58}, {'end': 351.592, 'text': 'uh, what is the next?', 'start': 350.511, 'duration': 1.081}, {'end': 354.312, 'text': 'uh, identical set, this one and this one.', 'start': 351.592, 'duration': 2.72}, {'end': 355.673, 'text': "let's write them down.", 'start': 354.312, 'duration': 1.361}, {'end': 363.255, 'text': 'so it says one one and this states zero comma three and zero comma four.', 'start': 355.673, 'duration': 7.582}, {'end': 368.256, 'text': 'right, and the other one is this and this, which is one comma one.', 'start': 363.255, 'duration': 5.001}], 'summary': 'Demonstration of subtracting sets and identifying identical sets with specific examples.', 'duration': 31.045, 'max_score': 337.211, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo337211.jpg'}], 'start': 3.168, 'title': 'Counting distinct islands', 'summary': 'Discusses the problem of finding the number of distinct islands in a boolean 2d matrix, where connected ones form an island horizontally or vertically. it also explains a method to store unique shapes in a set data structure to determine the number of unique shapes.', 'chapters': [{'end': 140.183, 'start': 3.168, 'title': 'Distinct islands problem', 'summary': 'Discusses the problem of finding the number of distinct islands in a boolean 2d matrix, where connected ones form an island horizontally or vertically, and islands are considered distinct if not rotated or reflected, with the solution involving identifying connected components and hashing to determine distinct islands.', 'duration': 137.015, 'highlights': ['The problem involves finding the number of distinct islands in a boolean 2D matrix, where connected ones form an island horizontally or vertically.', 'Islands are considered distinct if, and only if, one island is equal to the another, not rotated or reflected.', 'The solution to the problem involves identifying connected components and hashing to determine distinct islands.', 'Distinct islands are identified based on the shape of the island formed, and the number of distinct islands is counted accordingly.']}, {'end': 433.091, 'start': 141.061, 'title': 'Storing unique shapes in a set', 'summary': 'Explains a method to store unique shapes in a set data structure to determine the number of unique shapes, using examples and subtraction to identify identical shapes and calculate the size of the set.', 'duration': 292.03, 'highlights': ['The chapter explains a method to store unique shapes in a set data structure to determine the number of unique shapes The speaker discusses using a set data structure to store and count the number of unique shapes, emphasizing the need to identify a method for storing the shapes effectively.', 'using examples and subtraction to identify identical shapes and calculate the size of the set The speaker demonstrates using subtraction from a base point to identify identical shapes and create a list for storage in the set, providing examples to illustrate the process and ultimately determine the size of the set.']}], 'duration': 429.923, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo3168.jpg', 'highlights': ['The problem involves finding the number of distinct islands in a boolean 2D matrix, where connected ones form an island horizontally or vertically.', 'The solution to the problem involves identifying connected components and hashing to determine distinct islands.', 'Distinct islands are identified based on the shape of the island formed, and the number of distinct islands is counted accordingly.', 'The chapter explains a method to store unique shapes in a set data structure to determine the number of unique shapes.', 'The speaker discusses using a set data structure to store and count the number of unique shapes, emphasizing the need to identify a method for storing the shapes effectively.', 'The speaker demonstrates using subtraction from a base point to identify identical shapes and create a list for storage in the set, providing examples to illustrate the process and ultimately determine the size of the set.']}, {'end': 784.605, 'segs': [{'end': 459.087, 'src': 'embed', 'start': 433.091, 'weight': 0, 'content': [{'end': 444.798, 'text': "then, just to make sure you follow an order, if you're first going right, then down, then left, then up, please follow that order for everyone.", 'start': 433.091, 'duration': 11.707}, {'end': 449.982, 'text': "if you're going right and if you're following a particular traversal bfs, follow it throughout.", 'start': 444.798, 'duration': 5.184}, {'end': 459.087, 'text': "if you're following a particular traversal dfs, follow it throughout, so that the list ordering stays the same for everyone, like for here.", 'start': 449.982, 'duration': 9.105}], 'summary': 'Maintain consistent traversal order (right, down, left, up) for everyone.', 'duration': 25.996, 'max_score': 433.091, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo433091.jpg'}, {'end': 551.475, 'src': 'embed', 'start': 483.218, 'weight': 1, 'content': [{'end': 489.78, 'text': "If you'd have done a BFS, it would have been this, this, this, then this, this, this, then this, this, this.", 'start': 483.218, 'duration': 6.562}, {'end': 492.781, 'text': 'First like this, like this, then like this, then like this.', 'start': 490.56, 'duration': 2.221}, {'end': 493.761, 'text': "If you'd have done BFS.", 'start': 493.141, 'duration': 0.62}, {'end': 495.981, 'text': 'So you have to follow the same pattern.', 'start': 493.781, 'duration': 2.2}, {'end': 501.383, 'text': "If you're going first, follow the same pattern of traversal so that you traverse in the same manner.", 'start': 496.362, 'duration': 5.021}, {'end': 504.952, 'text': 'can be any part of the matrix.', 'start': 502.11, 'duration': 2.842}, {'end': 511.438, 'text': 'you travel in the same manner and you subtract the base to store the coordinates.', 'start': 504.952, 'duration': 6.486}, {'end': 514.561, 'text': 'you subtract the base to store the coordinates.', 'start': 511.438, 'duration': 3.123}, {'end': 515.481, 'text': 'super simple.', 'start': 514.561, 'duration': 0.92}, {'end': 520.826, 'text': "so you've got the intuition how to make sure that everything is stored.", 'start': 515.481, 'duration': 5.345}, {'end': 526.729, 'text': 'so one of the things we have figured out how to get the distinct islands.', 'start': 520.826, 'duration': 5.903}, {'end': 529.409, 'text': "we just need to store the islands, and it's very simple.", 'start': 526.729, 'duration': 2.68}, {'end': 534.591, 'text': "let's do a traversal, and we've already done this in the number of islands problem.", 'start': 529.409, 'duration': 5.182}, {'end': 539.132, 'text': 'you remember the number of islands problem if you do not pause and go back and watch it.', 'start': 534.591, 'duration': 4.541}, {'end': 541.392, 'text': 'so what you do is you start a traversal from here.', 'start': 539.132, 'duration': 2.26}, {'end': 544.993, 'text': "once you've started from here, visit all the guys connected to it.", 'start': 541.392, 'duration': 3.601}, {'end': 546.913, 'text': "so it'll go and visit this and this.", 'start': 544.993, 'duration': 1.92}, {'end': 551.475, 'text': "this can be stored in a set, in a list subtracting b's.", 'start': 546.913, 'duration': 4.562}], 'summary': 'Traverse matrix using bfs, store coordinates and find distinct islands.', 'duration': 68.257, 'max_score': 483.218, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo483218.jpg'}, {'end': 669.495, 'src': 'embed', 'start': 643.281, 'weight': 3, 'content': [{'end': 647.623, 'text': 'so again, this time the list will be created like zero, comma zero And 0,1..', 'start': 643.281, 'duration': 4.342}, {'end': 649.384, 'text': 'So, this list will again be stored in the set.', 'start': 647.623, 'duration': 1.761}, {'end': 652.746, 'text': 'In similar order, you can do the entire DFS traversal.', 'start': 649.744, 'duration': 3.002}, {'end': 656.167, 'text': 'Right? I hope you have understood the entire intuition and the thought process.', 'start': 653.086, 'duration': 3.081}, {'end': 657.488, 'text': 'It is very, very important.', 'start': 656.308, 'duration': 1.18}, {'end': 659.509, 'text': "So, let's get back to the code.", 'start': 657.928, 'duration': 1.581}, {'end': 664.092, 'text': 'As usual, the C++ code is in the right and the Java code will be on the left.', 'start': 659.85, 'duration': 4.242}, {'end': 669.495, 'text': 'So, count distinct islands and we are given the grid.', 'start': 664.772, 'duration': 4.723}], 'summary': 'Explaining dfs traversal and counting distinct islands in c++ and java.', 'duration': 26.214, 'max_score': 643.281, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo643281.jpg'}], 'start': 433.091, 'title': 'Traversal order and counting distinct islands', 'summary': 'Emphasizes the importance of maintaining a consistent traversal order using bfs or dfs to enable traversal in the same manner. it also discusses counting distinct islands using a dfs method, highlighting the significance of storing coordinates in sets and vectors for efficient tracking and counting.', 'chapters': [{'end': 504.952, 'start': 433.091, 'title': 'Consistent traversal order', 'summary': 'Emphasizes the importance of maintaining a consistent traversal order, whether using bfs or dfs, to ensure that the list ordering stays the same for everyone, thus enabling traversal in the same manner throughout the matrix.', 'duration': 71.861, 'highlights': ['Maintaining a consistent traversal order, whether using BFS or DFS, is crucial for ensuring the same list ordering for everyone, thus enabling traversal in the same manner throughout the matrix.', "Emphasizes the significance of following the same pattern of traversal, whether it's BFS or DFS, to ensure uniform traversal throughout the matrix.", 'Stresses the need to adhere to the same traversal pattern to maintain consistent traversal throughout the matrix.']}, {'end': 784.605, 'start': 504.952, 'title': 'Count distinct islands', 'summary': 'Discusses the process of counting distinct islands using a dfs traversal method, emphasizing the importance of storing coordinates in sets and vectors to effectively track and count distinct islands. it also provides insights into the importance of dfs and the utilization of sets and vectors for efficient traversal and storage.', 'duration': 279.653, 'highlights': ['The importance of storing coordinates in sets and vectors to effectively track and count distinct islands. Emphasizes the significance of storing coordinates in sets and vectors to ensure accurate tracking and counting of distinct islands.', 'Insights into the importance of DFS and the utilization of sets and vectors for efficient traversal and storage. Provides insights into the significance of DFS and the efficient utilization of sets and vectors for traversal and storage.', 'Discussion on the process of counting distinct islands using a DFS traversal method. Discusses the process of counting distinct islands using a DFS traversal method.']}], 'duration': 351.514, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo433091.jpg', 'highlights': ['Maintaining a consistent traversal order, whether using BFS or DFS, is crucial for ensuring the same list ordering for everyone, thus enabling traversal in the same manner throughout the matrix.', 'The importance of storing coordinates in sets and vectors to effectively track and count distinct islands.', "Emphasizes the significance of following the same pattern of traversal, whether it's BFS or DFS, to ensure uniform traversal throughout the matrix.", 'Insights into the importance of DFS and the utilization of sets and vectors for efficient traversal and storage.', 'Stresses the need to adhere to the same traversal pattern to maintain consistent traversal throughout the matrix.', 'Discussion on the process of counting distinct islands using a DFS traversal method.']}, {'end': 1072.87, 'segs': [{'end': 824.142, 'src': 'embed', 'start': 790.309, 'weight': 1, 'content': [{'end': 796.434, 'text': 'So go across and create a vector of int and an m, 0.', 'start': 790.309, 'duration': 6.125}, {'end': 804.656, 'text': "done. let's carry this on a vector of vector int visited, done.", 'start': 796.434, 'duration': 8.222}, {'end': 806.177, 'text': 'next, carry the grid.', 'start': 804.656, 'duration': 1.521}, {'end': 808.998, 'text': 'so just go ahead and carry the grid.', 'start': 806.177, 'duration': 2.821}, {'end': 812.539, 'text': "super simple once you've carried the grid, what will you carry?", 'start': 808.998, 'duration': 3.541}, {'end': 823.322, 'text': 'you need to carry something else, which is the vector, which will be the storing, the pairs and also done.', 'start': 812.539, 'duration': 10.783}, {'end': 824.142, 'text': "what's the first thing that you'll do?", 'start': 823.322, 'duration': 0.82}], 'summary': 'Creating vector of int and m, vector of vector int visited, and carrying the grid.', 'duration': 33.833, 'max_score': 790.309, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo790309.jpg'}, {'end': 892.716, 'src': 'embed', 'start': 847.435, 'weight': 0, 'content': [{'end': 850.898, 'text': 'So please carry these base coordinates always with you.', 'start': 847.435, 'duration': 3.463}, {'end': 857.922, 'text': 'So can I say the row 0 to be i and j? I can because those are the base coordinates and you store them.', 'start': 851.458, 'duration': 6.464}, {'end': 862.463, 'text': 'once you have done this, you have to travel in the upwards, the right words, the left words.', 'start': 858.522, 'duration': 3.941}, {'end': 865.384, 'text': 'so you need this del row kind of thing so you can again.', 'start': 862.463, 'duration': 2.921}, {'end': 868.905, 'text': 'you can declare this here or you can do it wherever you wish to.', 'start': 865.384, 'duration': 3.521}, {'end': 870.305, 'text': "i'm not going to explain this.", 'start': 868.905, 'duration': 1.4}, {'end': 871.246, 'text': 'from where did this come?', 'start': 870.305, 'duration': 0.941}, {'end': 874.787, 'text': "because i've already done this a lot of times in the graph series.", 'start': 871.246, 'duration': 3.541}, {'end': 878.588, 'text': "if you're watching this graph series for the first time, you're bad.", 'start': 874.787, 'duration': 3.801}, {'end': 880.168, 'text': 'you should go back and watch it.', 'start': 878.588, 'duration': 1.58}, {'end': 884.609, 'text': 'so now go to all the neighbors, which is something like anti zero.', 'start': 880.168, 'duration': 4.441}, {'end': 886.41, 'text': 'i, lesser than four i plus plus.', 'start': 884.609, 'duration': 1.801}, {'end': 892.716, 'text': 'get the neighboring row, which is something like row plus.', 'start': 888.052, 'duration': 4.664}], 'summary': 'Store base coordinates, travel up, right, left. iterate through neighbors.', 'duration': 45.281, 'max_score': 847.435, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo847435.jpg'}, {'end': 950.312, 'src': 'embed', 'start': 921.321, 'weight': 3, 'content': [{'end': 924.462, 'text': 'n row should not be visited.', 'start': 921.321, 'duration': 3.141}, {'end': 927.102, 'text': "and what's the next thing that you check should be a land.", 'start': 924.462, 'duration': 2.64}, {'end': 928.603, 'text': 'yes, should be a land.', 'start': 927.102, 'duration': 1.501}, {'end': 940.446, 'text': 'n row and n column should be a line done, And if it is, then you call the DFS for n row and n column.', 'start': 928.603, 'duration': 11.843}, {'end': 942.247, 'text': 'n column, not column.', 'start': 941.287, 'duration': 0.96}, {'end': 943.988, 'text': 'And then you pass the visited.', 'start': 942.747, 'duration': 1.241}, {'end': 945.589, 'text': 'Yes, you pass the grid.', 'start': 944.509, 'duration': 1.08}, {'end': 947.17, 'text': 'You pass the vector.', 'start': 946.33, 'duration': 0.84}, {'end': 948.511, 'text': 'You pass the row 0.', 'start': 947.55, 'duration': 0.961}, {'end': 950.312, 'text': 'You pass the column 0.', 'start': 948.511, 'duration': 1.801}], 'summary': 'Implement a dfs checking if a cell is land or not and calling dfs for each land cell. pass grid, vector, row 0, and column 0.', 'duration': 28.991, 'max_score': 921.321, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo921321.jpg'}, {'end': 1005.849, 'src': 'heatmap', 'start': 950.312, 'weight': 5, 'content': [{'end': 953.254, 'text': 'Once you have done this, I think we are pretty much done.', 'start': 950.312, 'duration': 2.942}, {'end': 954.635, 'text': "Let's quickly compile and see.", 'start': 953.594, 'duration': 1.041}, {'end': 960.652, 'text': "let's see if it is working fine.", 'start': 959.691, 'duration': 0.961}, {'end': 964.874, 'text': "it's giving some compilation error and looks like n was not declared.", 'start': 960.652, 'duration': 4.222}, {'end': 967.236, 'text': 'so again, do the same thing, just copy paste.', 'start': 964.874, 'duration': 2.362}, {'end': 971.188, 'text': 'so if we compile this we are getting the correct answer.', 'start': 968.547, 'duration': 2.641}, {'end': 974.59, 'text': "let's quickly submit this and check it does run.", 'start': 971.188, 'duration': 3.402}, {'end': 976.13, 'text': "so let's discuss these.", 'start': 974.59, 'duration': 1.54}, {'end': 979.912, 'text': 'uh, space complexity using a vector, visited and a set.', 'start': 976.13, 'duration': 3.782}, {'end': 988.656, 'text': "so it's going to be like the visited one is n cross m and if you store all the coordinates it's going to be n cross m for the set as well.", 'start': 979.912, 'duration': 8.744}, {'end': 991.637, 'text': 'so n cross m near about for the space complexity.', 'start': 988.656, 'duration': 2.981}, {'end': 992.358, 'text': 'what about the time?', 'start': 991.637, 'duration': 0.721}, {'end': 994.92, 'text': 'what are the time complexity?', 'start': 993.078, 'duration': 1.842}, {'end': 1001.765, 'text': 'n cross m over here and overall this dfs overall will be n cross m cross four.', 'start': 994.92, 'duration': 6.845}, {'end': 1005.849, 'text': "because overall, if you take all the cells, it's going to be n cross m cross four.", 'start': 1001.765, 'duration': 4.084}], 'summary': 'Discussion on space and time complexity of the code, with n cross m being the space complexity and n cross m cross four as the time complexity.', 'duration': 55.537, 'max_score': 950.312, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo950312.jpg'}, {'end': 1061.759, 'src': 'heatmap', 'start': 1014.857, 'weight': 0.706, 'content': [{'end': 1026.294, 'text': 'so n cross m can say something like n cross m for the loop and then n cross m cross for overall for this entire dfs call.', 'start': 1014.857, 'duration': 11.437}, {'end': 1038.859, 'text': 'and then you can attach a logarithmic term to it into logarithmic offset length, which is this the set at max will store all of these guys.', 'start': 1026.294, 'duration': 12.565}, {'end': 1040.521, 'text': 'so you can say n cross m.', 'start': 1038.859, 'duration': 1.662}, {'end': 1046.933, 'text': 'logarithmic of set length is n cross m, because at max it is going to store all these guys.', 'start': 1041.451, 'duration': 5.482}, {'end': 1051.915, 'text': 'so overall, this is the for loop and this is the dfs time complexity.', 'start': 1046.933, 'duration': 4.982}, {'end': 1053.496, 'text': 'so, guys, i hope i was so.', 'start': 1051.915, 'duration': 1.581}, {'end': 1056.577, 'text': 'guys, i hope i was able to explain you this, uh, complex question.', 'start': 1053.496, 'duration': 3.081}, {'end': 1059.538, 'text': 'so just in case i was please hit that like button.', 'start': 1056.577, 'duration': 2.961}, {'end': 1061.759, 'text': "and if you're new to our channel, what are you waiting for?", 'start': 1059.538, 'duration': 2.221}], 'summary': 'The time complexity of the algorithm is o(n*m*log(n*m)), explained in a tutorial.', 'duration': 46.902, 'max_score': 1014.857, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo1014857.jpg'}, {'end': 1053.496, 'src': 'embed', 'start': 1026.294, 'weight': 7, 'content': [{'end': 1038.859, 'text': 'and then you can attach a logarithmic term to it into logarithmic offset length, which is this the set at max will store all of these guys.', 'start': 1026.294, 'duration': 12.565}, {'end': 1040.521, 'text': 'so you can say n cross m.', 'start': 1038.859, 'duration': 1.662}, {'end': 1046.933, 'text': 'logarithmic of set length is n cross m, because at max it is going to store all these guys.', 'start': 1041.451, 'duration': 5.482}, {'end': 1051.915, 'text': 'so overall, this is the for loop and this is the dfs time complexity.', 'start': 1046.933, 'duration': 4.982}, {'end': 1053.496, 'text': 'so, guys, i hope i was so.', 'start': 1051.915, 'duration': 1.581}], 'summary': 'The time complexity is o(n * m) for the for loop and dfs.', 'duration': 27.202, 'max_score': 1026.294, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo1026294.jpg'}], 'start': 790.309, 'title': 'Grid traversal and dfs implementation', 'summary': 'Covers the algorithm for grid traversal, emphasizing base coordinate creation, storage, and traversal in different directions, with a reference to the graph series. it also discusses the implementation of a dfs algorithm, ensuring constraints, space complexity of n cross m for vector, visited, and set, and time complexity of n cross m for the dfs.', 'chapters': [{'end': 892.716, 'start': 790.309, 'title': 'Grid traversal algorithm', 'summary': 'Covers the algorithm for grid traversal, emphasizing the creation and storage of base coordinates and the traversal process in different directions, with a reference to the graph series and a recommendation to watch it for better understanding.', 'duration': 102.407, 'highlights': ['The chapter emphasizes the need to carry and store base coordinates for grid traversal to calculate neighboring coordinates, which is crucial for the algorithm (e.g., row - base coordinates, column - base coordinates).', "The process of grid traversal involves marking the coordinates as visited, moving in different directions (upwards, rightwards, leftwards), and accessing neighboring coordinates, iterating through all neighbors (e.g., iterating through all neighbors using 'anti zero' and accessing neighboring row using 'row plus').", 'The chapter refers to the graph series, hinting at the importance of prior knowledge and experience in graph-related algorithms and techniques, suggesting that viewers should revisit the graph series for better understanding.']}, {'end': 976.13, 'start': 892.716, 'title': 'Dfs algorithm implementation', 'summary': 'Discusses the implementation of a dfs algorithm to traverse a grid, ensuring constraints such as n row and n column being within bounds, and checking for unvisited cells and land before recursively calling the dfs function.', 'duration': 83.414, 'highlights': ['The first step involves checking if n row, n column, and not visited are within bounds and if the cell is a land, before recursively calling the DFS function, ensuring the constraints for traversal (n row > 0, n row < n, 0 <= n column < m).', 'The importance of checking for unvisited cells is emphasized, as it is a crucial step in the traversal process.', "Compiling the code initially results in a compilation error due to an undeclared variable 'n', which is resolved by copying and pasting the code, leading to successful compilation and submission of the program."]}, {'end': 1072.87, 'start': 976.13, 'title': 'Space and time complexity analysis', 'summary': 'Discusses the space complexity of n cross m for vector, visited, and set, and the time complexity of n cross m for the dfs, and n cross m cross four for the overall dfs call, along with logarithmic complexity for the set length.', 'duration': 96.74, 'highlights': ['The space complexity is n cross m for the vector, visited, and set, with n cross m for the overall DFS call.', 'The time complexity is n cross m for the DFS, and n cross m cross four for the overall DFS call, with additional logarithmic complexity for the set length.', 'The set at max will store all n cross m coordinates, resulting in a logarithmic complexity of n cross m.']}], 'duration': 282.561, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/7zmgQSJghpo/pics/7zmgQSJghpo790309.jpg', 'highlights': ['The chapter emphasizes the need to carry and store base coordinates for grid traversal to calculate neighboring coordinates, crucial for the algorithm.', 'The process of grid traversal involves marking the coordinates as visited, moving in different directions, and accessing neighboring coordinates, iterating through all neighbors.', 'The chapter refers to the graph series, hinting at the importance of prior knowledge and experience in graph-related algorithms and techniques.', 'The first step involves checking if n row, n column, and not visited are within bounds and if the cell is a land, before recursively calling the DFS function, ensuring the constraints for traversal.', 'The importance of checking for unvisited cells is emphasized, as it is a crucial step in the traversal process.', 'The space complexity is n cross m for the vector, visited, and set, with n cross m for the overall DFS call.', 'The time complexity is n cross m for the DFS, and n cross m cross four for the overall DFS call, with additional logarithmic complexity for the set length.', 'The set at max will store all n cross m coordinates, resulting in a logarithmic complexity of n cross m.']}], 'highlights': ['The problem involves finding the number of distinct islands in a boolean 2D matrix, where connected ones form an island horizontally or vertically.', 'The solution to the problem involves identifying connected components and hashing to determine distinct islands.', 'The process of grid traversal involves marking the coordinates as visited, moving in different directions, and accessing neighboring coordinates, iterating through all neighbors.', "Emphasizes the significance of following the same pattern of traversal, whether it's BFS or DFS, to ensure uniform traversal throughout the matrix.", 'The importance of storing coordinates in sets and vectors to effectively track and count distinct islands.', 'The chapter emphasizes the need to carry and store base coordinates for grid traversal to calculate neighboring coordinates, crucial for the algorithm.', 'The space complexity is n cross m for the vector, visited, and set, with n cross m for the overall DFS call.', 'The time complexity is n cross m for the DFS, and n cross m cross four for the overall DFS call, with additional logarithmic complexity for the set length.']}