title

G-9. Flood Fill Algorithm | C++ | Java

description

GfG Problem Link: https://bit.ly/3bxY94d
C++/Java/Codes and Notes Link: https://takeuforward.org/graph/flood-fill-algorithm-graphs/
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-9. Flood Fill Algorithm | C++ | Java', 'heatmap': [{'end': 1061.208, 'start': 1019.818, 'weight': 0.9}], 'summary': 'Covers the flood fill algorithm, matrix coloring, blood fill, dfs algorithm, and image color fill algorithm, emphasizing the dfs preference, time complexity of o(n*m), and space complexity of o(n*m), with a total of four neighbors to consider in the neighbor check.', 'chapters': [{'end': 182.58, 'segs': [{'end': 65.358, 'src': 'embed', 'start': 23.013, 'weight': 0, 'content': [{'end': 25.175, 'text': 'how are we approaching this problem?', 'start': 23.013, 'duration': 2.162}, {'end': 28.738, 'text': 'because it is again going to be a problem which is based on matrix.', 'start': 25.175, 'duration': 3.563}, {'end': 38.124, 'text': 'So it states that an image is represented by 2D RF integers, each integer representing the pixel value of the image.', 'start': 29.298, 'duration': 8.826}, {'end': 43.107, 'text': 'Given a coordinate SR, SC representing the starting pixel.', 'start': 38.844, 'duration': 4.263}, {'end': 45.849, 'text': 'So basically SR is the row and SC is the column.', 'start': 43.367, 'duration': 2.482}, {'end': 50.552, 'text': 'So this is the starting pixel of the flood fill and a pixel value new color.', 'start': 46.369, 'duration': 4.183}, {'end': 52.553, 'text': 'Flood fill the image.', 'start': 51.152, 'duration': 1.401}, {'end': 54.633, 'text': 'Now to perform a flood fill.', 'start': 53.213, 'duration': 1.42}, {'end': 64.797, 'text': 'consider the starting pixel plus any pixels connecting four directionally to the starting pixel of the same color as the starting pixel plus any pixels connected four directionally to those pixels,', 'start': 54.633, 'duration': 10.164}, {'end': 65.358, 'text': 'and so on.', 'start': 64.797, 'duration': 0.561}], 'summary': 'Problem: flood fill an image using 2d rf integers.', 'duration': 42.345, 'max_score': 23.013, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o23013.jpg'}], 'start': 3.217, 'title': 'Flood fill algorithm', 'summary': 'Explains the flood fill algorithm, involving filling a matrix with a new color from a given coordinate, extending in four directions, and replacing the color of connected pixels with the new color.', 'chapters': [{'end': 182.58, 'start': 3.217, 'title': 'Flood fill algorithm explained', 'summary': 'Explains the flood fill algorithm, which involves filling a matrix with a new color starting from a given coordinate and extending in four directions, ultimately replacing the color of connected pixels with the new color.', 'duration': 179.363, 'highlights': ['The flood fill algorithm involves filling a matrix with a new color starting from a given coordinate, and extending in four directions to replace the color of connected pixels with the new color.', 'The algorithm can be solved using BFS or DFS, and it is based on a matrix represented by 2D integers, with each integer representing the pixel value of the image.', 'The starting pixel of the flood fill is represented by a coordinate (SR, SC), where SR is the row and SC is the column, and the process involves coloring connected pixels with the new color based on the starting pixel.']}], 'duration': 179.363, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o3217.jpg', 'highlights': ['The flood fill algorithm involves filling a matrix with a new color starting from a given coordinate, and extending in four directions to replace the color of connected pixels with the new color.', 'The algorithm can be solved using BFS or DFS, and it is based on a matrix represented by 2D integers, with each integer representing the pixel value of the image.', 'The starting pixel of the flood fill is represented by a coordinate (SR, SC), where SR is the row and SC is the column, and the process involves coloring connected pixels with the new color based on the starting pixel.']}, {'end': 364.467, 'segs': [{'end': 212.512, 'src': 'embed', 'start': 182.58, 'weight': 6, 'content': [{'end': 184.947, 'text': 'so let me give you One more example.', 'start': 182.58, 'duration': 2.367}, {'end': 186.668, 'text': 'So assume you have something like 1, 1, 1.', 'start': 185.107, 'duration': 1.561}, {'end': 190.593, 'text': 'And you had something like 2.', 'start': 186.669, 'duration': 3.924}, {'end': 191.073, 'text': 'And this was 2.', 'start': 190.593, 'duration': 0.48}, {'end': 192.335, 'text': 'This was 0.', 'start': 191.073, 'duration': 1.262}, {'end': 195.278, 'text': 'Assume And this was 2.', 'start': 192.335, 'duration': 2.943}, {'end': 195.878, 'text': 'This was 2.', 'start': 195.278, 'duration': 0.6}, {'end': 196.879, 'text': 'And this was 2.', 'start': 195.878, 'duration': 1.001}, {'end': 199.102, 'text': 'And they said the new color that you have to pick up.', 'start': 196.879, 'duration': 2.223}, {'end': 202.865, 'text': 'The new color, rather that you have to do is 3, okay?', 'start': 199.682, 'duration': 3.183}, {'end': 208.389, 'text': "And they're saying the starting row to be 2 and the starting column to be 0..", 'start': 203.525, 'duration': 4.864}, {'end': 209.51, 'text': 'Assume that this is the case.', 'start': 208.389, 'duration': 1.121}, {'end': 212.512, 'text': "So if I draw the matrix, let's draw the matrix.", 'start': 209.95, 'duration': 2.562}], 'summary': 'Given a matrix with values, the task is to find a new color to pick up at position (2, 0).', 'duration': 29.932, 'max_score': 182.58, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o182580.jpg'}, {'end': 319.028, 'src': 'embed', 'start': 251.459, 'weight': 0, 'content': [{'end': 254.441, 'text': 'But only this guy is having the same initial color.', 'start': 251.459, 'duration': 2.982}, {'end': 257.161, 'text': 'So thereby, you color this with 3.', 'start': 254.841, 'duration': 2.32}, {'end': 260.184, 'text': 'Perfect Now this 3 is connected to 4 directions.', 'start': 257.161, 'duration': 3.023}, {'end': 264.026, 'text': 'But only this guy is having the same initial color too.', 'start': 260.724, 'duration': 3.302}, {'end': 264.807, 'text': 'So you color this.', 'start': 264.266, 'duration': 0.541}, {'end': 271.052, 'text': 'Apparently, this will be the final configuration because these guys are connected, but this is 1110.', 'start': 265.487, 'duration': 5.565}, {'end': 273.294, 'text': 'So you do not color them.', 'start': 271.052, 'duration': 2.242}, {'end': 279.84, 'text': "You only color the guy who's connected by the same initial color that you're coloring this particular guy.", 'start': 273.595, 'duration': 6.245}, {'end': 287.667, 'text': 'This is how you can blood fill any given matrix by starting from a row and a column.', 'start': 280.281, 'duration': 7.386}, {'end': 295.199, 'text': 'So how do you solve this? So as of now, we can see that this is the starting row and this is the starting column, which is this particular guy.', 'start': 287.968, 'duration': 7.231}, {'end': 303.222, 'text': 'So what are we looking for? We are looking to basically extend this to these guys, then to these guys, and then to these guys.', 'start': 295.779, 'duration': 7.443}, {'end': 304.783, 'text': 'That is what we are looking for.', 'start': 303.682, 'duration': 1.101}, {'end': 312.245, 'text': 'So which algorithm can we follow? We can follow one kind of algorithm, which is breadth-first search.', 'start': 305.243, 'duration': 7.002}, {'end': 319.028, 'text': 'And breadth-first search says that we start at the given point, we go on level-wise.', 'start': 312.826, 'duration': 6.202}], 'summary': 'A matrix can be filled using breadth-first search algorithm, connecting cells based on initial color.', 'duration': 67.569, 'max_score': 251.459, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o251459.jpg'}, {'end': 364.467, 'src': 'embed', 'start': 339.853, 'weight': 3, 'content': [{'end': 347.196, 'text': 'So we can definitely use something like a BFS algorithm where we go simultaneously on all its neighbors.', 'start': 339.853, 'duration': 7.343}, {'end': 355.501, 'text': 'or what i can do is i can use something like a dfs algorithm, because the previous problem we solved using dfs.', 'start': 347.896, 'duration': 7.605}, {'end': 360.704, 'text': 'so this problem we will be focusing to solve using dfs, so that you understand that.', 'start': 355.501, 'duration': 5.203}, {'end': 362.565, 'text': 'why does dfs work over here?', 'start': 360.704, 'duration': 1.861}, {'end': 363.586, 'text': 'so over here?', 'start': 362.565, 'duration': 1.021}, {'end': 364.467, 'text': "it's nothing like that.", 'start': 363.586, 'duration': 0.881}], 'summary': 'Using dfs algorithm to solve problem, focusing on its efficiency.', 'duration': 24.614, 'max_score': 339.853, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o339853.jpg'}], 'start': 182.58, 'title': 'Matrix coloring, blood fill, and graph algorithm comparison', 'summary': 'Covers the matrix coloring problem with initial color 2 and new color 3, blood fill algorithm for coloring connected matrix elements, and compares bfs and dfs algorithms, emphasizing dfs preference.', 'chapters': [{'end': 228.199, 'start': 182.58, 'title': 'Matrix coloring problem', 'summary': 'Discusses the matrix coloring problem with an example where the initial color is 2, and the new color to be picked up is 3, with starting row 2 and starting column 0.', 'duration': 45.619, 'highlights': ['The new color that needs to be picked up is 3, and the starting row is 2 and the starting column is 0.', 'An example of a matrix with initial color 2 and the new color to be picked up is 3 is discussed.']}, {'end': 295.199, 'start': 228.199, 'title': 'Blood fill algorithm', 'summary': 'Illustrates the blood fill algorithm for coloring connected elements in a matrix, starting from a given row and column, by identifying and coloring adjacent elements with the same color, resulting in the final configuration by following specific rules.', 'duration': 67, 'highlights': ['The blood fill algorithm involves coloring connected elements in a matrix with the same color, starting from a specified row and column, and identifying adjacent elements with the same initial color to be colored, resulting in the final configuration (relevance: 5)', 'The algorithm specifies that only elements connected by the same initial color should be colored, leading to a specific final configuration, as demonstrated in the example (relevance: 4)', 'The process of applying the blood fill algorithm is exemplified by identifying and coloring adjacent elements with the same color, showcasing the step-by-step approach to achieve the final configuration (relevance: 3)']}, {'end': 364.467, 'start': 295.779, 'title': 'Graph algorithm comparison: bfs vs dfs', 'summary': 'Discusses the comparison between breadth-first search (bfs) and depth-first search (dfs) algorithms for graph traversal, highlighting their applications and differences in approach, while emphasizing the preference for dfs in the context of the problem.', 'duration': 68.688, 'highlights': ['DFS algorithm is preferred over BFS for the current problem, based on its successful application in a previous problem, providing a focused approach for graph traversal.', 'Explanation of breadth-first search (BFS) algorithm, emphasizing its level-wise traversal and simultaneous coloring of nodes, showcasing its potential for graph traversal.', 'Consideration of extending the application of the algorithms to different groups, indicating the scalability and adaptability of both breadth-first search (BFS) and depth-first search (DFS) in handling diverse graph structures.']}], 'duration': 181.887, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o182580.jpg', 'highlights': ['The blood fill algorithm involves coloring connected elements in a matrix with the same color, starting from a specified row and column, and identifying adjacent elements with the same initial color to be colored, resulting in the final configuration (relevance: 5)', 'The algorithm specifies that only elements connected by the same initial color should be colored, leading to a specific final configuration, as demonstrated in the example (relevance: 4)', 'The process of applying the blood fill algorithm is exemplified by identifying and coloring adjacent elements with the same color, showcasing the step-by-step approach to achieve the final configuration (relevance: 3)', 'DFS algorithm is preferred over BFS for the current problem, based on its successful application in a previous problem, providing a focused approach for graph traversal.', 'Explanation of breadth-first search (BFS) algorithm, emphasizing its level-wise traversal and simultaneous coloring of nodes, showcasing its potential for graph traversal.', 'Consideration of extending the application of the algorithms to different groups, indicating the scalability and adaptability of both breadth-first search (BFS) and depth-first search (DFS) in handling diverse graph structures.', 'The new color that needs to be picked up is 3, and the starting row is 2 and the starting column is 0.', 'An example of a matrix with initial color 2 and the new color to be picked up is 3 is discussed.']}, {'end': 479.097, 'segs': [{'end': 391.302, 'src': 'embed', 'start': 364.467, 'weight': 1, 'content': [{'end': 368.809, 'text': 'you have to, uh, color them in a minimum time or something like that.', 'start': 364.467, 'duration': 4.342}, {'end': 373.412, 'text': 'the question says at the end of the day i need the final configuration.', 'start': 368.809, 'duration': 4.603}, {'end': 374.493, 'text': 'so the, the,', 'start': 373.412, 'duration': 1.081}, {'end': 389.1, 'text': 'So the requirement is at the end of the day you just need to make sure everything that is touched to this two and is two is colored with three.', 'start': 375.529, 'duration': 13.571}, {'end': 391.302, 'text': 'That is what you want at the end.', 'start': 389.601, 'duration': 1.701}], 'summary': 'Color all items touched by two with three by the end of the day.', 'duration': 26.835, 'max_score': 364.467, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o364467.jpg'}, {'end': 479.097, 'src': 'embed', 'start': 437.91, 'weight': 0, 'content': [{'end': 445.156, 'text': 'so you say dfs of 2, comma 0 is where you start off with and when you are starting off you need the final color.', 'start': 437.91, 'duration': 7.246}, {'end': 447.038, 'text': 'right, you need the final color.', 'start': 445.156, 'duration': 1.882}, {'end': 453.543, 'text': 'so either you can use the same matrix, but i generally do not prefer to alter the input matrix.', 'start': 447.038, 'duration': 6.505}, {'end': 459.487, 'text': 'why? because Whenever you go into the industry, whenever data is given to you, you work on that data.', 'start': 453.543, 'duration': 5.944}, {'end': 462.888, 'text': 'You do not tamper with the data because data is very, very important.', 'start': 459.507, 'duration': 3.381}, {'end': 467.531, 'text': 'So we always have to treat the data as the data and we do not tamper with it.', 'start': 463.168, 'duration': 4.363}, {'end': 470.572, 'text': 'Something that is given to us, we should never tamper with it.', 'start': 467.771, 'duration': 2.801}, {'end': 476.095, 'text': 'We should always solve the problem without doing any alteration to that particular data.', 'start': 470.853, 'duration': 5.242}, {'end': 479.097, 'text': 'That is something which we follow in software engineering a lot.', 'start': 476.115, 'duration': 2.982}], 'summary': 'Start with dfs of 2,0 for final color. avoid altering input data in software engineering.', 'duration': 41.187, 'max_score': 437.91, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o437910.jpg'}], 'start': 364.467, 'title': 'Dfs algorithm for coloring problem', 'summary': 'Discusses the depth-first search (dfs) algorithm for coloring problem, emphasizing the importance of not altering input data in software engineering.', 'chapters': [{'end': 479.097, 'start': 364.467, 'title': 'Dfs algorithm for coloring problem', 'summary': 'Discusses the depth-first search (dfs) algorithm for coloring problem, emphasizing the importance of not altering input data in software engineering.', 'duration': 114.63, 'highlights': ['The requirement is to ensure that everything touched to two and is two is colored with three, implying a transformation in color for specific elements.', 'The algorithm involves utilizing DFS to traverse through the elements and making sure not to alter the input matrix, in accordance with the principles of software engineering.', 'Emphasizing the significance of not tampering with given data in software engineering to maintain data integrity and solve problems without altering the original data.']}], 'duration': 114.63, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o364467.jpg', 'highlights': ['The algorithm involves utilizing DFS to traverse through the elements and making sure not to alter the input matrix, in accordance with the principles of software engineering.', 'The requirement is to ensure that everything touched to two and is two is colored with three, implying a transformation in color for specific elements.', 'Emphasizing the significance of not tampering with given data in software engineering to maintain data integrity and solve problems without altering the original data.']}, {'end': 750.711, 'segs': [{'end': 564.154, 'src': 'embed', 'start': 533.915, 'weight': 1, 'content': [{'end': 536.436, 'text': "so we'll try to go first in this portion of depth.", 'start': 533.915, 'duration': 2.521}, {'end': 540.818, 'text': 'it could have gone the either way, depending on how you are writing the code.', 'start': 536.436, 'duration': 4.382}, {'end': 543.139, 'text': 'it can go on this or on this.', 'start': 540.818, 'duration': 2.321}, {'end': 546.942, 'text': 'so we will see that it goes on this dfs of one zero.', 'start': 543.139, 'duration': 3.803}, {'end': 551.224, 'text': 'so again you go to one zero, which is this, and you color that with the new color.', 'start': 546.942, 'duration': 4.282}, {'end': 558.77, 'text': 'now this one zero is having one children and these children are not having the same color.', 'start': 551.224, 'duration': 7.546}, {'end': 564.154, 'text': "it's not two, and this is invalid, and this has already been visited.", 'start': 558.77, 'duration': 5.384}], 'summary': 'Traversing code depth, coloring nodes, and invalid cases encountered.', 'duration': 30.239, 'max_score': 533.915, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o533915.jpg'}, {'end': 645.382, 'src': 'embed', 'start': 584.412, 'weight': 0, 'content': [{'end': 586.735, 'text': "so let's color that with the new color three.", 'start': 584.412, 'duration': 2.323}, {'end': 590.079, 'text': 'now, since it is colored, it will look for its neighbor.', 'start': 586.735, 'duration': 3.344}, {'end': 591.821, 'text': 'no, it is one.', 'start': 590.079, 'duration': 1.742}, {'end': 593.643, 'text': 'no, it is zero.', 'start': 591.821, 'duration': 1.822}, {'end': 596.346, 'text': 'this one already visited this one.', 'start': 593.643, 'duration': 2.703}, {'end': 601.398, 'text': 'yes, it is too, and it has not been visited.', 'start': 597.236, 'duration': 4.162}, {'end': 606.439, 'text': 'it will be visited, but that dfs has not been called yet.', 'start': 601.398, 'duration': 5.041}, {'end': 611.101, 'text': 'it will be visited, but it was supposed to take two sites.', 'start': 606.439, 'duration': 4.662}, {'end': 616.283, 'text': 'but since it is dfs, since it is dfs, it will go like this.', 'start': 611.101, 'duration': 5.182}, {'end': 621.785, 'text': 'then, like this and like this dfs depth first search at first.', 'start': 616.283, 'duration': 5.502}, {'end': 631.152, 'text': 'okay. so what will happen is this dfs of one will now call for dfs of two, comma one, and it will mark this as three.', 'start': 621.785, 'duration': 9.367}, {'end': 638.898, 'text': 'now this this guy looks at its neighbor, already visited, looks at it neighbor not visited.', 'start': 631.152, 'duration': 7.746}, {'end': 642.74, 'text': 'so does a visit for this, which is dfs of two.', 'start': 638.898, 'duration': 3.842}, {'end': 645.382, 'text': 'comma two goes there and marks it.', 'start': 642.74, 'duration': 2.642}], 'summary': 'Dfs algorithm explores nodes, marking and visiting them in a specific order.', 'duration': 60.97, 'max_score': 584.412, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o584412.jpg'}], 'start': 480.526, 'title': 'Depth first search algorithm', 'summary': 'Provides an explanation of the depth first search algorithm with examples, discussing its working process, including node coloring and traversal in a depth-first manner.', 'chapters': [{'end': 750.711, 'start': 480.526, 'title': 'Depth first search algorithm explanation', 'summary': 'Explains the depth first search algorithm with examples and discusses how it works, including the process of coloring nodes with new colors and traversing through the graph in a depth-first manner.', 'duration': 270.185, 'highlights': ['Depth First Search algorithm is explained with examples and discusses the process of coloring nodes and traversing the graph in a depth-first manner.', 'The algorithm involves coloring nodes with new colors and traversing through the graph in a depth-first manner.', 'The chapter discusses the principles of the Depth First Search algorithm and provides examples of traversing through the graph in a depth-first manner.']}], 'duration': 270.185, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o480526.jpg', 'highlights': ['The algorithm involves coloring nodes with new colors and traversing through the graph in a depth-first manner.', 'Depth First Search algorithm is explained with examples and discusses the process of coloring nodes and traversing the graph in a depth-first manner.', 'The chapter discusses the principles of the Depth First Search algorithm and provides examples of traversing through the graph in a depth-first manner.']}, {'end': 1082.438, 'segs': [{'end': 818.68, 'src': 'embed', 'start': 750.731, 'weight': 0, 'content': [{'end': 752.392, 'text': "We're given the starting this.", 'start': 750.731, 'duration': 1.661}, {'end': 755.735, 'text': 'So the first thing that we do is we keep the initial color.', 'start': 752.893, 'duration': 2.842}, {'end': 758.677, 'text': 'What will be the initial color? Definitely this.', 'start': 756.095, 'duration': 2.582}, {'end': 759.798, 'text': "There's no doubt in this.", 'start': 759.057, 'duration': 0.741}, {'end': 764.401, 'text': 'What is the next thing that we do? We copy this particular image.', 'start': 761.139, 'duration': 3.262}, {'end': 768.525, 'text': 'Because we need to flat fill it and return it.', 'start': 765.402, 'duration': 3.123}, {'end': 769.946, 'text': 'So we will copy this.', 'start': 768.925, 'duration': 1.021}, {'end': 772.182, 'text': 'into some answer.', 'start': 771.161, 'duration': 1.021}, {'end': 774.783, 'text': 'okay, perfect, do we need something else?', 'start': 772.182, 'duration': 2.601}, {'end': 776.804, 'text': 'really we can think about that afterwards.', 'start': 774.783, 'duration': 2.021}, {'end': 784.249, 'text': "let's call the dfs, starting from the starting row, starting column, give him the answer, give him the image, and if we require something else,", 'start': 776.804, 'duration': 7.445}, {'end': 785.79, 'text': 'we will take that afterwards.', 'start': 784.249, 'duration': 1.541}, {'end': 793.454, 'text': 'okay, so we write a private function and the private function will have void dfs and it knows it has at a row,', 'start': 785.79, 'duration': 7.664}, {'end': 798.578, 'text': 'it has at a column and it has this particular answer at first.', 'start': 793.454, 'duration': 5.124}, {'end': 802.108, 'text': 'okay, and then it has this particular image.', 'start': 799.406, 'duration': 2.702}, {'end': 806.351, 'text': 'so that is something which it always has initially.', 'start': 802.108, 'duration': 4.243}, {'end': 814.397, 'text': 'now what we will do is, if you remember well enough, whenever we entered, whenever we entered on this row column,', 'start': 806.351, 'duration': 8.046}, {'end': 817.339, 'text': 'we always colored it with the new color.', 'start': 814.397, 'duration': 2.942}, {'end': 818.68, 'text': 'we need the new color as well.', 'start': 817.339, 'duration': 1.341}], 'summary': 'Dfs algorithm used to flat fill and return an image with new color.', 'duration': 67.949, 'max_score': 750.731, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o750731.jpg'}, {'end': 893.969, 'src': 'embed', 'start': 864.318, 'weight': 2, 'content': [{'end': 876.944, 'text': 'so either you can write four calls separately, one by one by one, but to maintain readability what you will do is we will try to figure out a way.', 'start': 864.318, 'duration': 12.626}, {'end': 884.186, 'text': 'so we see, there is a change of minus one in the row, a change of plus zero in the row, a change of plus one in the row,', 'start': 876.944, 'duration': 7.242}, {'end': 885.726, 'text': 'a change of plus zero in the row.', 'start': 884.186, 'duration': 1.54}, {'end': 893.969, 'text': 'so what i can say is delta change in row is minus one, zero plus one and zero.', 'start': 885.726, 'duration': 8.243}], 'summary': 'Delta change in row is -1, 0, +1, 0.', 'duration': 29.651, 'max_score': 864.318, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o864318.jpg'}, {'end': 1001.92, 'src': 'embed', 'start': 959.981, 'weight': 3, 'content': [{'end': 963.987, 'text': 'this is going to be an array, so please carry as this as an array done.', 'start': 959.981, 'duration': 4.006}, {'end': 965.929, 'text': 'it travels on all its neighbors.', 'start': 963.987, 'duration': 1.942}, {'end': 967.331, 'text': 'so how many neighbors are there?', 'start': 965.929, 'duration': 1.402}, {'end': 969.114, 'text': 'there are exactly four neighbors.', 'start': 967.331, 'duration': 1.783}, {'end': 971.557, 'text': 'so please carry them.', 'start': 969.114, 'duration': 2.443}, {'end': 973.88, 'text': 'perfect. now, what is the next thing that you will do?', 'start': 971.557, 'duration': 2.323}, {'end': 975.642, 'text': 'you need the neighbor row.', 'start': 973.88, 'duration': 1.762}, {'end': 980.907, 'text': 'so, neighbor, you know what is that row plus del row of i correct.', 'start': 975.642, 'duration': 5.265}, {'end': 982.268, 'text': 'and you know what is the column.', 'start': 980.907, 'duration': 1.361}, {'end': 987.171, 'text': 'it is column plus del column of i, right, we know that.', 'start': 982.268, 'duration': 4.903}, {'end': 992.795, 'text': 'so once you have got the neighbor row and the neighbor column, what should be your main focus?', 'start': 987.171, 'duration': 5.624}, {'end': 997.357, 'text': 'your main focus should be first of all is this a valid guy?', 'start': 992.795, 'duration': 4.562}, {'end': 1000.92, 'text': "because if it is not a valid guy, there's no point in doing the first thing.", 'start': 997.357, 'duration': 3.563}, {'end': 1001.92, 'text': 'we need this.', 'start': 1000.92, 'duration': 1}], 'summary': 'Code discussion on array neighbors, with 4 neighbors, and validity check.', 'duration': 41.939, 'max_score': 959.981, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o959981.jpg'}, {'end': 1061.208, 'src': 'heatmap', 'start': 1019.818, 'weight': 0.9, 'content': [{'end': 1025.816, 'text': "and then So, once you've checked for validity, you need to check is this guy?", 'start': 1019.818, 'duration': 5.998}, {'end': 1029.038, 'text': 'yes, is this guy having the same initial color?', 'start': 1025.816, 'duration': 3.222}, {'end': 1030.839, 'text': 'Then only they will be connected.', 'start': 1029.538, 'duration': 1.301}, {'end': 1040.685, 'text': 'And at the same time, has this previously been visited and colored? If it has been previously visited, then it will definitely have the new color.', 'start': 1031.259, 'duration': 9.426}, {'end': 1046.388, 'text': 'If it does not have the new color yet, and it is the same color, then I go and test.', 'start': 1041.185, 'duration': 5.203}, {'end': 1048.402, 'text': 'color it?', 'start': 1047.622, 'duration': 0.78}, {'end': 1061.208, 'text': "yes, simple, it's a new column and then what we can do is we can pass the answer image again, new color del row del column and the initial color.", 'start': 1048.402, 'duration': 12.806}], 'summary': 'Validating and coloring connections based on initial color and previous visits.', 'duration': 41.39, 'max_score': 1019.818, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o1019818.jpg'}, {'end': 1061.208, 'src': 'embed', 'start': 1025.816, 'weight': 4, 'content': [{'end': 1029.038, 'text': 'yes, is this guy having the same initial color?', 'start': 1025.816, 'duration': 3.222}, {'end': 1030.839, 'text': 'Then only they will be connected.', 'start': 1029.538, 'duration': 1.301}, {'end': 1040.685, 'text': 'And at the same time, has this previously been visited and colored? If it has been previously visited, then it will definitely have the new color.', 'start': 1031.259, 'duration': 9.426}, {'end': 1046.388, 'text': 'If it does not have the new color yet, and it is the same color, then I go and test.', 'start': 1041.185, 'duration': 5.203}, {'end': 1048.402, 'text': 'color it?', 'start': 1047.622, 'duration': 0.78}, {'end': 1061.208, 'text': "yes, simple, it's a new column and then what we can do is we can pass the answer image again, new color del row del column and the initial color.", 'start': 1048.402, 'duration': 12.806}], 'summary': 'Checking if the guy has same initial color, if previously visited, then it will definitely have the new color.', 'duration': 35.392, 'max_score': 1025.816, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o1025816.jpg'}], 'start': 750.731, 'title': 'Image color fill algorithm', 'summary': 'Discusses an algorithm for filling colors in an image using depth-first search (dfs) and private functions, emphasizing the process of copying, starting and returning an image, and defining parameters for the dfs function. it also covers implementing a neighbor check in code, involving the computation of delta changes in row and column and the validation of neighbors, with a total of four neighbors to consider.', 'chapters': [{'end': 818.68, 'start': 750.731, 'title': 'Image color fill algorithm', 'summary': 'Discusses an algorithm for filling colors in an image using depth-first search (dfs) and private functions, emphasizing the process of copying, starting and returning an image, and defining parameters for the dfs function.', 'duration': 67.949, 'highlights': ['The algorithm involves keeping the initial color of the image, copying the image for flat filling, and utilizing a private function with void dfs, starting from a given row and column, and returning the image. The process emphasizes the importance of the new color and the initial parameters for the DFS function.', 'The chapter emphasizes the significance of the initial color and the copying process in the image color fill algorithm, while also highlighting the use of private functions and the depth-first search (DFS) approach for effective color filling.']}, {'end': 1082.438, 'start': 818.68, 'title': 'Implementing neighbor check in code', 'summary': 'Discusses implementing a neighbor check in code, involving the computation of delta changes in row and column and the validation of neighbors, with a total of four neighbors to consider.', 'duration': 263.758, 'highlights': ['The chapter discusses implementing a neighbor check in code, involving the computation of delta changes in row and column.', 'It explains the process of validating neighbors, with a total of four neighbors to consider.', 'The speaker emphasizes the importance of checking for validity before proceeding with the neighbor computation.', 'The code checks if the neighbor has the same initial color and if it has been previously visited and colored.']}], 'duration': 331.707, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o750731.jpg', 'highlights': ['The algorithm involves keeping the initial color of the image, copying the image for flat filling, and utilizing a private function with void dfs, starting from a given row and column, and returning the image.', 'The chapter emphasizes the significance of the initial color and the copying process in the image color fill algorithm, while also highlighting the use of private functions and the depth-first search (DFS) approach for effective color filling.', 'The chapter discusses implementing a neighbor check in code, involving the computation of delta changes in row and column.', 'It explains the process of validating neighbors, with a total of four neighbors to consider.', 'The code checks if the neighbor has the same initial color and if it has been previously visited and colored.', 'The process emphasizes the importance of the new color and the initial parameters for the DFS function.', 'The speaker emphasizes the importance of checking for validity before proceeding with the neighbor computation.']}, {'end': 1225.095, 'segs': [{'end': 1207.696, 'src': 'embed', 'start': 1133.187, 'weight': 0, 'content': [{'end': 1137.108, 'text': "So I can say you're calling the code for like X nodes right?", 'start': 1133.187, 'duration': 3.921}, {'end': 1140.727, 'text': "for every node you're traversing for four guys.", 'start': 1137.725, 'duration': 3.002}, {'end': 1150.554, 'text': "so it's like you're calling dfs for x times, because at max there will be these many dfs calls and for every x guy you're calling like four,", 'start': 1140.727, 'duration': 9.827}, {'end': 1152.555, 'text': "like you're running a four loop.", 'start': 1150.554, 'duration': 2.001}, {'end': 1154.296, 'text': 'so it can again be written.', 'start': 1152.555, 'duration': 1.741}, {'end': 1159.92, 'text': 'as we go of x, which is somewhere, we go of n cross m.', 'start': 1154.296, 'duration': 5.624}, {'end': 1162.422, 'text': 'so this will be the time complexity.', 'start': 1159.92, 'duration': 2.502}, {'end': 1170.026, 'text': 'and if we discuss about the space complexity, we are using an external matrix to store the answer.', 'start': 1162.422, 'duration': 7.604}, {'end': 1173.388, 'text': 'again you can say that you will store the answer in the given matrix.', 'start': 1170.026, 'duration': 3.362}, {'end': 1175.709, 'text': 'only. that is your choice.', 'start': 1173.388, 'duration': 2.321}, {'end': 1180.112, 'text': "apart from that, there is something as a stack space that you're using.", 'start': 1175.709, 'duration': 4.403}, {'end': 1185.314, 'text': 'so that is like in the recursive stack space, that is, we go off n cross n.', 'start': 1180.112, 'duration': 5.202}, {'end': 1192.058, 'text': 'imagine you start the dfs from here and the recursion will go here, here, here, here, here, here, here, here.', 'start': 1185.314, 'duration': 6.744}, {'end': 1192.919, 'text': "so it'll be.", 'start': 1192.578, 'duration': 0.341}, {'end': 1193.519, 'text': 'the recursion.', 'start': 1192.919, 'duration': 0.6}, {'end': 1196.183, 'text': 'stack space will be complete n cross m.', 'start': 1193.519, 'duration': 2.664}, {'end': 1199.727, 'text': "that is the another space that you're using.", 'start': 1196.183, 'duration': 3.544}, {'end': 1204.072, 'text': "and apart from that, you're using this delta row and delta column, so you can compute that easily.", 'start': 1199.727, 'duration': 4.345}, {'end': 1207.696, 'text': 'so, guys, i hope i was able to explain you the flood fill algorithm,', 'start': 1204.072, 'duration': 3.624}], 'summary': 'The time complexity is o(n * m) and space complexity is o(n * m), using external matrix and recursive stack space in the flood fill algorithm.', 'duration': 74.509, 'max_score': 1133.187, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o1133187.jpg'}], 'start': 1082.738, 'title': 'Time and space complexity of flood fill algorithm', 'summary': 'Discusses the time complexity of o(n*m) and space complexity of o(n*m) of the flood fill algorithm, with additional stack space being o(n*m), involving calling the code for x nodes and traversing for four neighbors for each node.', 'chapters': [{'end': 1225.095, 'start': 1082.738, 'title': 'Time and space complexity of flood fill algorithm', 'summary': 'Discusses the time complexity of the flood fill algorithm, which is o(n*m), and the space complexity, which is o(n*m) as well, with additional stack space being o(n*m). the algorithm involves calling the code for x nodes and traversing for four neighbors for each node.', 'duration': 142.357, 'highlights': ['The time complexity of the flood fill algorithm is O(n*m), where n represents the number of rows and m represents the number of columns in the matrix.', 'The space complexity of the flood fill algorithm involves using an external matrix to store the answer and additional stack space in the recursive stack, both being O(n*m).', 'The algorithm involves calling the code for X nodes and traversing for four neighbors for each node, which contributes to the time complexity of O(n*m).', 'The space complexity also includes using delta row and delta column, contributing to the overall space complexity of O(n*m).', 'The chapter also highlights the usage of external matrices and stack space, along with the explanation of the flood fill algorithm and a call-to-action for viewers to engage with the channel content.']}], 'duration': 142.357, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/C-2_uSRli8o/pics/C-2_uSRli8o1082738.jpg', 'highlights': ['The time complexity of the flood fill algorithm is O(n*m), where n represents the number of rows and m represents the number of columns in the matrix.', 'The space complexity of the flood fill algorithm involves using an external matrix to store the answer and additional stack space in the recursive stack, both being O(n*m).', 'The algorithm involves calling the code for X nodes and traversing for four neighbors for each node, which contributes to the time complexity of O(n*m).', 'The space complexity also includes using delta row and delta column, contributing to the overall space complexity of O(n*m).', 'The chapter also highlights the usage of external matrices and stack space, along with the explanation of the flood fill algorithm and a call-to-action for viewers to engage with the channel content.']}], 'highlights': ['The flood fill algorithm involves filling a matrix with a new color starting from a given coordinate, and extending in four directions to replace the color of connected pixels with the new color.', 'The blood fill algorithm involves coloring connected elements in a matrix with the same color, starting from a specified row and column, and identifying adjacent elements with the same initial color to be colored, resulting in the final configuration (relevance: 5)', 'The algorithm involves utilizing DFS to traverse through the elements and making sure not to alter the input matrix, in accordance with the principles of software engineering.', 'The time complexity of the flood fill algorithm is O(n*m), where n represents the number of rows and m represents the number of columns in the matrix.']}