[Leetcode]733. Flood Fill

📄 Description

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

🔨 My Solution

• check the current pixel and paint, plus check the adjacent pixels of the same color.
  1. the pixel should be valid one
  2. the color of the pixel should be same color
• repeat this painting process through DFS

💻 My Submission

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        dr=[-1,1,0,0]
        dc=[0,0,-1,1]
        r,c=len(image),len(image[0])
        
        check=[[False]*c for _ in range(r)]
        color=image[sr][sc]
        
        def recur(i,j):
            check[i][j]=True
            
            if image[i][j]==color:
                image[i][j]=newColor
            
            for k in range(4):
                nr=i+dr[k]
                nc=j+dc[k]
                #print(nr,nc)
                
                if nc<0 or nc>=c or nr<0 or nr>=r:
                    continue
                
                if not check[nr][nc] and image[nr][nc]==color:
                    recur(nr,nc)    
        recur(sr,sc)
        
        
        return image

🔎 Complexity

Time Complexity: O(N)
where N is the number of pixels in the image.
Space Complexity: O(N)
the size of the implicit call stack when calling dfs.

💊 Clean code

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        R, C = len(image), len(image[0])
        color = image[sr][sc]
        if color == newColor: return image
        def dfs(r, c):
            if image[r][c] == color:
                image[r][c] = newColor
                if r >= 1: dfs(r-1, c)
                if r+1 < R: dfs(r+1, c)
                if c >= 1: dfs(r, c-1)
                if c+1 < C: dfs(r, c+1)

        dfs(sr, sc)
        return image

💡 How can I improve my solution?

1. Without using dr and dc, we can split the four adjacent position to if condition and dfs each of them.
2. I used check array for checking if the pixel have been already checked, to avoid checking again. And I'm curious if it is efficient for decreasing time..?

References
https://leetcode.com/problems/flood-fill/solution/