Flood Fill Algorithm || Programm 49 || Competitive Coding || Learning Monkey ||

Flood Fill Algorithm
In this class, We discuss Flood Fill Algorithm.
Readers can prepare an entire competitive coding course to crack product development companies. Click Here.
The reader should have basic coding skills to work with competitive coding. Click here.
Question:
We represent an image as a two-dimensional array of integers.
The pixel values are in the array.
Input: Given row and column value for one of the pixels and new pixel value.
Flood Fill: Convert the starting pixel colour to a new colour.
Take the pixel UP, DOWN, RIGHT, and LEFT from the starting pixel.
If any of the four pixels have the same starting pixel colour, change the pixel value to a new colour.
Continue the process to change the possible pixels.
Example:
The below diagram shows an example of input and output.
The starting pixel row and column values are [4, 1].
New color = 2
Time complexity: O(N X M)
Space Complexity: O(N+M)
Logic:
We can do this using recursive functions and using Loops.
Each function will call four functions to check the UP, DOWN, RIGHT, and LEFT pixels.
Using loops, we can use a queue data structure to store the coordinates.
We provided a step-by-step explanation in the video.
Code: less than and greater than symbols are changed to lt and gt
class Solution:
def color(self,image,i,j,newColor,m,n,startColor) :
if ilt0 or igt=m or jlt0 or jgt=n or image[i][j] != startColor or image[i][j] == newColor :
return
image[i][j] = newColor
self.color(image,i+1,j,newColor,m,n,startColor)
self.color(image,i,j+1,newColor,m,n,startColor)
self.color(image,i-1,j,newColor,m,n,startColor)
self.color(image,i,j-1,newColor,m,n,startColor)

def floodFill(self, image, sr, sc, newColor):
m = len(image)
n = len(image[0])
startColor = image[sr][sc]
self.color(image,sr,sc,newColor,m,n,startColor)
return image
screen =[
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 1, 1],
[1, 2, 2, 2, 2, 0, 1, 0],
[1, 1, 1, 2, 2, 0, 1, 0],
[1, 1, 1, 2, 2, 2, 2, 0],
[1, 1, 1, 1, 1, 2, 1, 1],
[1, 1, 1, 1, 1, 2, 2, 1],
]
sr=4
sc=4
ob=Solution()
z=ob.floodFill(screen,sr, sc, 3)
m=len(z)
n=len(z[0])
for i in range(m):
for j in range(n):
print(z[i][j], end =' ')
print()
Link for playlists:
/ @learningmonkey
Link for our website: learningmonkey.in
Follow us on Facebook @ / learningmonkey
Follow us on Instagram @ / learningmonkey1
Follow us on Twitter @ / _learningmonkey
Mail us @ [e-mail]